package com.windcoder.javaWork.work.chapter2;

import java.util.HashMap;
import java.util.Map;

/**
 * [560. 和为 K 的子数组](https://leetcode-cn.com/problems/subarray-sum-equals-k/)
 */
public class SubarraySum {

    // 方案一：循环遍历-枚举
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int nowSum = 0,count=0;
        for (int i=0;i<len;i++) {
            nowSum=0;
            for (int j=i;j<len;j++) {
                nowSum= nowSum+nums[j];
                if (nowSum==k) {
                    count++;
                }
            }

        }

        return count;
    }

    /**
     * 方案二：前缀和-字段和
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum2(int[] nums, int k) {
        int count=0,pre = 0,len = nums.length;
        Map<Integer,Integer> map = new HashMap<>(); // 记录前n项和出现的次数
        map.put(0,1);
        for (int i=0;i<len;i++) {
            pre+=nums[i]; //前n项和 S[i]
            // k=S[i]-S[j-1] => S[j-1] = S[i]-k = pre-k
            if (map.containsKey(pre-k)) {
                count+=map.get(pre-k);
            }
            map.put(pre, map.getOrDefault(pre,0)+1);
        }

        return count;
    }


    public static void main(String[] args) {
//        int[] str = new int[] {-916,-132,-202,-524,739,57,938,546,948,-181,-315,921,792,-992,-69,588,712,509,-406,302,-637,169,407,993,-263,54,-512,-950,-930,66,147,-9,-136,-205,274,992,-304,-835,659,-792,-288,146,182,-672,-374,-943,-85,958,-19,33,-676,232,92,-132,-121,-944,-526,-869,-423,-855,818,46,401,633,-457,63,824,-172,237,360,43,831,-432,213,-330,-788,-472,-70,-507,615,-953,457,-89,-756,477,445,153,-779,710,484,-20,802,-261,-481,-309,-992,-240,275,-302,-137,295,-232,529,691,873,787,229,677,-388,996,301,-641,-983,108,-247,431,-668,877,528,-69,-15,278,-334,775,770,-720,232,-607,896,496,485,350,772,-656,379,730,-445,-152,295,99,-945,-170,-594,271,894,-451,-455,636,-210,674,554,183,446,-709,-599,521,711,-739,-712,-947,-940,-577,71,672,-512,-216,669,137,-61,-901,-867,-168,-838,-653,-503,-535,-423,-922,281,544,-373,-935,-485,760,-203,-656,-241,493,-290,-298,756,-871,-525,614,230,-910,-395,-308,-237,289,975,-215,542,674,798,95,-989,912,-943,-262,-501,-670,-878,-40,983,963,-136,682,-383,-537,-724,382,-831,726,91,666,-795,308,-519,-891,-313,960,-785,-629,519,783,-2,705,-658,993,656,795,441,145,-298,411,-593,-738,-701,-453,857,769,-841,-609,248,-315,-465,-2,93,748,-75,-227,-426,-446,428,54,324,-72,-340,-361,-327,204,991,-720,-861,-33,-517,454,241,-34,-750,-31,-476,-428,909,-221,-981,168,352,-443,-733,821,-287,395,691,-230,45,-752,-524,-998,-245,-947,560,308,-144,223,-802,844,-321,194,-666,-960,-920,-668,989,-735,-566,-298,652,215,916,862,261,-894,-984,124,348,-858,-571,585,681,-197,387,-308,-349,-555,-530,993,464,-285,-195,-786,777,-819,-45,-792,200,994,82,832,-70,-578,-244,-546,-866,-746,563,-359,-857,-610,-518,-902,-746,540,-721,184,-523,-64,466,-166,719,-76,937,-150,-55,849,-42,-403,-492,-24,-850,-448,-460,167,596,-799,523,-699,975,104,658,-274,462,618,-320,-330,-639,-541,-218,-627,-303,-504,781,-564,967,-635,-523,-918,-529,705,624,-196,814,-165,142,-103,935,573,45,-377,661,-521,691,-81,-496,-883,995,227,592,606,-756,183,-486,-767,-68,648,666,-134,977,617,-545,735,-502,-730,779,-744,-123,-495,-848,937,-227,-470,401,-909,-135,884,484,326,-910,953,-321,352,134,-683,855,199,-966,-900,290,-575,-194,828,743,-762,-846,530,-603,679,132,380,-596,110,-678,842,505,-925,993,-765,374,-694,-346,656,-332,-131,-846,-196,34,408,-612,-701,316,-803,-123,-417,887,823,-696,850,762,-231,-863,-758,-782,-504,670,164,-878,-260,561,-448,37,660,-776,787,782,-712,31,-106,485,-345,-802,-512,-305,776,796,788,-575,-577,-268,38,356,-221,649,378,-128,-779,317,313,673,-494,-126,92,910,-343,675,857,-850,-322,-607,318,-694,523,-880,-800,936,204,-275,-822,-528,928,-242,-420,-769,39,982,-373,517,332,-459,-408,-125,-15,304,56,777,-52,496,-610,-877,-308,-876,-148,266,-441,-341,-489,-214,276,27,-413,-534,-805,-607,-808,-568,73,532,732,689,-653,-489,-198,383,851,452,-47,-987,-549,379,-693,-921,-428,-261,707,777,-969,728,-868,341,803,-593,241,122,551,-523,-189,461,-447,130,242,-71,582,-86,16,110,579,-519,-434,-904,27,-359,986,955,783,-195,-911,-29,744,-390,808,-666,-24,962,114,873,473,162,73,-366,975,-207,419,225,-809,656,-85,536,-417,345,-940,805,48,335,967,790,258,-546,-179,-34,651,257,-111,-456,912,251,-639,-24,-638,50,-536,90,112,812,-504,346,553,-571,830,-511,-340,-464,566,-594,-953,715,-697,538,-709,230,-949,-547,-982,-183,238,82,20,-600,-16,47,917,269,-895,768,714,391,104,577,951,510,-226,85,347,-263,-8,100,-670,295,788,-645,-191,534,856,248,568,961,820,-570,552,-772,-892,-109,-312,-979,631,-688,830,-164,-942,-431,898,-358,907,-186,-350,753,-199,-15,-657,-426,-382,53,688,-971,-245,748,703,-633,-232,178,-8,-923,225,-925,-715,-666,-264,-411,-966,-423,-330,633,642,718,690,-434,770,689,902,597,-877,543,-358,-510,93,191,588,-65,-822,-75,857,871,-266,-965,-577,-533,158,-971,-993,615,242,230,-580,-352,611,-684,-280,812,32,-57,651,-916,-733,-763,112,556,102,-283,855,-398,267,839,-527,-58,-64,-68,303,10,16,242,241,-305,-2,927,-41,-71,-362,118,61,-250,454,-801,-479,-518,-659,432,577,799,515,-127,237,597,-907,-597,912,955,-181,-595,455,-626,-383,712,-742,-774,-63,-351,-680,-577,706,868,-306,-778,92,718,-746,-512,310,-534,-868,-546,-32,499,-15,-358,-171,909,-151,357,471,-284,928,8,-186,743,-230,-632,-282,-211,274,68,-88,-979,-12,-673,580,-156,250,903,918,-589,492,446,-133,412,-445,-125,-164,-736,112,-240,-815,-832,991,-965,28,-956,-879,143,346,420,8,-672,-142,-942,347,-844,720,-622,-473,-46,-163,-735,734,-471,-269,-526,-911,-732,-913,966,64,-992,-407,-503,-648,763,850,-637,628,-376,-315,-134,476,-740,533,-481,504,476,-651,936,-750,16,-871,-225,-750,-1,639,114,-862,-390,776,-401,667,-519,-52,774,-143,491,-805,-316,469,-584,979,-143,535,438,935,-619,-191,-974,597,-349,-682,-922,-403,535,109,82,-544,960,397,-858,-489,57,-544,-285,806,300,-753,-86,-411,186,-652,178,909,-756,712,25,-677,86,-156,622,-503,862,-127,-281,700,158,474,-655,512,920,917,760,879,-538,384,-210,-501,-617,300,970,266,514,293,291,586,-308,-24,821,576,267,32,780,341,637,914,822,197,629,456,-774,864,84,-179,973,772,-963,-579,-961,294,-293,846,-97,-685,-462,-183,536,493,927,871,990,-154,-478,300,-486,-827,677,796,433,-184,77,745,-651,-938,-614,193,-21,-644,303,283,-831,631,607,66,168,447,830,28,886,-827,-108,-70,-230,-937,602,206,453,382,-105,-997,780,-292,857,794,-409,-24,-82,408,-606,617,-271,-7,832,385,73,-786,-868,-711,823,-10,549,-765,226,-792,914,179,-293,-122,-31,419,344,-401,359,-321,157,-865,628,995,-738,731,336,-335,658,-337,852,-665,977,-302,680,-161,-404,-146,703,-162,633,-234,-389,-931,955,807,-170,-83,-245,736,-314,-869,-736,970,-326,491,-783,-182,174,-985,-248,25,-657,802,-849,929,-618,-720,206,-316,839,-406,64,54,-819,195,93,985,513,230,-545,969,509,-844,323,667,376,885,-979,561,71,-880,35,657,926,-562,804,-940,479,485,-734,976,186,339,806,65,-163,-849,-76,968,569,44,255,868,382,911,73,16,-164,548,-919,-344,-533,-831,825,-856,159,129,-900,-116,-469,-807,-197,198,-775,144,696,842,62,-273,129,847,149,407,-681,-831,-656,-551,871,-329,-466,-379,-874,780,541,322,232,-332,-170,-829,-673,-833,-741,-308,709,701,-383,-810,-651,69,-917,420,613,494,783,23,-317,-143,-670,167,-486,459,-327,-545,-172,135,970,-352,-825,661,901,-184,-52,128,-426,407,-302,-612,-766,-999,900,645,-373,647,-828,704,-812,-847,794,-525,816,-450,-240,-400,-351,-78,479,771,-262,-311,108,197,-368,361,-226,-428,-220,966,783,-374,25,377,-978,-593,-807,-559,-950,876,-684,760,261,590,-929,-746,-382,834,404,-384,31,-168,-338,860,800,850,20,-267,-691,998,-765,-651,-205,-354,-166,-758,-85,543,-298,-831,364,4,-171,-555,-22,940,-124,-134,-432,-70,475,939,880,336,122,210,-444,968,819,-320,-248,-830,817,-798,584,389,291,203,804,838,-511,112,206,340,556,593,698,449,-874,693,187,-78,-840,100,705,569,432,-366,-834,-440,-90,975,991,809,-953,493,580,550,-764,-560,561,248,810,688,-738,946,-818,385,597,400,-973,-241,-35,63,-268,735,653,240,7,846,937,534,-724,913,747,-891,72,439,-818,519,-416,-527,803,-112,180,-878,192,225,944,-828,-410,966,-399,-839,-889,345,-815,-421,-425,958,-843,621,-800,-646,774,247,825,-624,392,285,-701,414,-298,341,-489,302,864,-267,-95,-170,-383,415,-964,718,950,-500,108,526,969,-830,-363,-739,-946,-500,-249,910,-465,133,346,-303,149,271,674,-474,473,-50,803,-179,358,10,984,-92,708,-2,-562,-596,607,-378,-995,829,-252,320,850,-574,165,-637,143,-240,108,-532,847,812,-540,-983,-804,903,-387,-707,-431,376,-131,325,-30,507,638,663,134,125,-614,-411,154,-564,426,-948,-990,-28,548,-265,-673,-212,857,-568,-921,422,-362,-359,-699,879,194,598,-857,225,-453,-137,-476,-712,-576,-347,363,835,-433,98,-306,94,585,486,-977,195,648,-257,637,143,-878,-395,990,-983,110,-550,660,776,824,-566,-844,531,525,632,-755,77,-846,-394,208,130,-162,-750,279,-490,25,762,84,-579,-14,-666,-27,540,-692,0,180,306,95,-214,826,333,-375,913,530,293,-12,664,-533,932,-566,207,-494,-667,200,195,-259,-966,564,-430,176,20,-909,462,656,-470,723,-530,-757,-331,67,516,407,-790,-989,-219,435,-473,818,-470,-590,-71,-324,-342,-843,743,-912,-105,-665,432,-316,-615,-295,87,726,74,516,145,-436,681,-434,-601,67,790,-727,-915,419,-747,252,-764,-583,-937,640,-373,157,-179,913,719,841,812,-548,-197,-301,420,662,357,-192,-656,-581,611,481,-185,-666,192,176,-874,-599,685,-993,-691,22,-815,293,698,-4,-7,-119,511,-415,700,-400,-21,808,687,913,-277,-566,-881,-367,626,429,-821,-728,565,-995,-446,146,-928,658,-807,415,265,-218,984,-121,258,872,851,-88,-432,-812,-267,-615,342,826,-4,-148,546,274,-415,-178,260,466,-960,729,-784,249,689,958,-700,-866,-970,-626,-936,-637,469,119,-342,984,242,923,754,-278,-583,924,-789,-283,-216,574,531,-572,-873,164,-29,-874,475,-528,-663,30,23,958,756,-79,-38,998,-698,504,948,-213,-122,497,-396,-839,-684,-700,-689,-181,106,-295,538,-936,-764,-298,-264,-986,-418,-639,-714,-834,293,771,-711,504,-581,123,805,-587,-524,-257,-197,-505,-649,-182,-344,978,59,319,508,-543,48,-269,-517,-604,292,201,973,-490,104,-549,-914,663,279,-977,842,-901,107,-858,-201,550,877,-257,-608,-109,401,-880,-339,-815,-41,711,733,-295,465,217,84,-890,-370,-590,350,-103,-750,-808,424,-846,248,520,-768,369,-953,652,-202,422,-831,-978,334,349,-352,-759,-615,872,-712,-887,-286,-384,540,-609,755,285,486,-888,241,380,777,641,897,434,-114,-726,-720,477,347,708,26,-797,-46,-75,608,545,-850,-386,-112,-243,95,-245,565,996,691,-697,28,799,358,474,-402,68,715,980,-168,487,-23,505,368,654,885,990,-526,-335,460,976,270,933,578,168,626,458,-974,598,991,-710,673,759,-838,-380,177,683,-831,582,724,472,454,367,-995,85,-110,321,-919,788,-625,-421,-195,-790,-790,370,-890,306,379,21,-418,69,-374,-110,-170,-993,849,-356,927,-281,-452,-137,-351,232,67,-326,-53,18,164,833,-42,-966,950,402,-819,739,551,-759,-27,432,-152,850,330,820,426,-840,693,-955,993,-469,-238,-997,-334,319,-318,-984,113,523,-591,436,-870,162,84,626,494,881,639,-651,-439,-190,515,279,-503,534,334,544,219,-931,590,719,-237,852,-982,-963,860,-242,-106,-795,897,-295,-334,-732,-289,9,-643,546,748,714,182,383,180,-146,954,820,564,839,-137,571,-169,-331,-140,-615,-93,-466,767,-479,-144,421,581,-844,134,193,38,889,-418,135,-742,452,-104,-717,-301,899,-465,-788,569,-570,676,-174,428,62,-342,-311,211,548,344,642,-50,-135,-976,207,-365,676,272,-56,125,655,746,808,131,-583,-55,-439,95,747,599,-306,719,-84,-525,147,539,-322,996,-6,348,551,486,685,838,119,545,959,-911,-849,124,237,333,912,-554,943,-221,-445,-912,149,-620,513,-336,-331,809,-185,-906,-365,543,-895,690,221,-48,374,898,-996,988,925,554,906,815,-493,-823,451,87,682,862,-334,378,656,-372,-648,337,-420,563,155,185,385,-269,-695,579,-244,390,-519,947,35,-366,-447,-639,401,515,-811,-940,191,-430,417,12,-114,316,-929,384,-619,-947,580,-276,-400,180,75,-969,-289,187,-547,667,-624,471,433,-433,426,-749,-298,939,-678,-730,129,679,-232,-219,360,-424,889,441,-55,380,-570,117,-471,928,87,231,476,-327,-883,-883,-848,701,-205,-405,-921,-154,542,-946,144,-551,-537,-328,974,-873,-599,-691,668,153,789,-813,612,65,535,935,488,-246,534,-519,-477,672,785,-89,507,-867,-447,350,-546,979,266,349,-32,966,669,750,586,-272,-407,604,722,-545,164,863,-245,-469,372,507,-492,-226,-909,-83,893,418,759,-697,-835,507,382,-779,729,601,471,-685,798,-1000,-237,567,913,956,-441,-123,682,-184,-55,847,-197,984,521,-931,268,-460,298,903,-571,-329,459,-448,-9,289,386,-993,-282,197,74,612,-377,-104,-307,97,303,-15,-932,-960,800,188,-537,-39,-739,349,972,-769,-164,672,-216,-803,181,754,923,433,-757,-576,-950,-57,783,637,-534,626,-220,524,169,-672,-743,-329,974,-221,-595,-531,-839,-360,249,411,-366,-674,-62,724,192,-222,-613,552,-380,61,427,-566,613,44,-91,-318,-278,-96,226,-954,225,307,-909,-864,-260,-594,209,153,212,-345,-597,-603,-834,-385,254,10,989,-431,434,-430,628,-954,-25,-314,709,-464,-19,-196,-730,-419,737,947,-150,-978,17,682,-30,-530,118,-82,87,357,52,18,-669,772,692,-532,-483,-308,-701,-868,-941,520,-160,866,-147,31,980,210,-870,824,31,719,-285,738,-267,-728,-370,-631,-633,-889,255,-993,169,-631,-215,-228,530,402,-980,-357,424,-125,-870,532,341,-699,242,986,-470,-906,675,-576,398,52,-958,0,-688,-380,-165,-548,-575,429,-105,-361,298,-471,-774,875,-749,166,867,-40,-605,146,210,-96,-791,607,-494,-459,-675,-96,798,-332,-207,606,73,415,-23,-571,-317,-655,-6,-293,505,674,526,-295,63,910,-304,621,247,-260,549,-731,527,940,141,-505,-157,131,-857,-571,-615,68,418,-870,-665,73,-615,-200,-102,-633,-24,-489,-753,-51,153,-442,-603,642,-357,-410,-965,-621,460,782,682,-355,104,-836,-212,46,200,839,410,-628,-87,344,714,-197,-378,963,-231,-600,299,-401,-21,118,-881,-843,29,-264,596,-356,-968,408,450,-254,-968,698,-631,992,-622,57,-927,301,729,-619,-794,-459,362,902,867,983,950,924,175,-729,-790,847,625,-183,-240,-365,-99,624,501,731,269,22,61,-187,422,141,289,-747,113,872,494,432,170,823,-665,-187,-825,-980,721,960,-23,-975,-796,-921,102,400,760,520,-585,-238,-125,-556,-397,-132,-380,877,-703,149,273,-866,470,83,-613,581,925,437,318,-740,-546,243,173,223,-983,838,309,-303,356,425,737,569,-489,-94,-277,-789,-923,-593,689,-743,-352,-608,542,559,339,662,296,643,-285,128,862,701,642,357,12,-55,-398,96,20,948,-205,109,-754,-855,-836,-541,392,-340,-817,23,-80,212,-532,-287,36,914,-594,-771,78,-221,703,-636,-714,757,-147,548,353,700,693,-587,685,176,790,-8,-316,-765,312,-628,-236,392,-181,417,-213,667,-578,-432,210,-57,545,-811,425,550,153,-952,-45,302,-761,-948,-312,-67,-121,-366,-641,-994,-680,-168,-164,-440,-930,811,69,-199,-363,-872,230,-858,533,-210,-901,700,-177,-238,380,-311,758,794,-845,983,-930,909,-947,99,182,-831,-375,-146,-336,-65,985,818,91,422,959,825,194,429,361,-684,-937,350,993,-825,817,-828,-398,233,-392,-37,644,727,615,440,-501,750,622,-136,-615,-173,861,-175,740,279,-812,-839,515,803,7,574,-25,-705,-147,-41,955,-699,-188,-749,257,774,-812,-427,145,43,-33,-871,934,230,-796,-652,-304,-895,-892,-667,419,-777,-201,132,-147,304,791,-792,-203,144,721,-949,-863,127,342,-374,-29,-468,977,-482,588,-767,403,610,646,-782,757,-185,-500,-723,382,-478,-181,716,670,95,546,-145,428,-521,-292,7,36,714,-376,391,560,-776,34,747,-135,295,447,6,-948,-336,607,-564,366,55,265,441,-930,669,-872,752,29,859,-297,-935,-279,-810,691,-783,-882,468,717,-396,885,374,10,640,63,-895,515,-387,897,-827,220,556,453,678,-750,754,-442,-80,-447,-425,52,-2,-484,171,551,-241,-576,473,35,-199,-58,522,654,133,-859,-983,-70,156,837,956,-852,667,-201,-383,857,-561,342,-377,-689,-705,-847,633,-698,-545,207,961,384,470,955,-955,201,819,-775,-732,-282,-860,751,-474,248,401,-515,-620,628,639,992,-639,908,-285,901,-899,-503,293,-167,-20,-20,856,-1,853,-401,-397,435,831,-984,357,921,-206,-4,398,-688,-597,767,549,720,896,-657,-604,-651,-81,580,762,-990,-479,838,-924,383,-894,-902,615,911,687,-504,-120,-251,-467,614,-676,377,-98,707,137,859,274,635,19,668,-548,-705,-371,388,648,-484,806,-430,947,405,-599,101,72,-452,-834,-413,-69,-516,841,330,661,-70,857,925,620,-776,168,-176,141,284,383,-75,283,-93,63,325,345,354,432,307,303,-271,668,-463,-318,-615,-798,-160,443,139,-161,656,-340,86,-129,16,-204,-272,-84,591,770,22,-641,-497,-521,-964,-625,-335,517,879,844,124,781,-635,-510,202,753,924,112,-416,-77,-244,-310,883,400,-533,749,419,589,995,683,613,-121,-614,652,-247,631,3,399,-974,552,581,-544,-120,-45,-720,105,293,370,678,387,825,122,-635,-153,460,-657,-452,904,-164,-663,-203,-121,888,198,-715,-717,-662,498,952,821,-797,-326,560,-70,-680,-7,-726,-436,-674,-143,268,411,-989,-831,-959,883,830,-693,-366,782,390,829,193,409,913,-34,-455,584,312,27,218,-203,677,847,172,-581,-394,-133,229,-984,-894,-54,148,553,812,-560,48,67,41,413,772,-305,-332,-227,-731,62,-739,-929,918,214,-963,224,-397,736,16,-202,335,145,-86,-312,-731,-984,215,-684,958,-534,-208,270,-988,405,344,670,-24,358,-916,-259,-570,514,212,466,-758,-556,149,462,-120,931,-953,-478,-557,-929,-474,560,297,223,522,-695,477,-986,-786,-453,-270,550,772,225,784,-704,-471,-9,323,-383,-402,-752,227,929,-950,497,744,-558,-75,943,32,604,-901,289,-486,-747,-520,-871,-533,-510,451,633,955,-276,358,-166,206,254,-438,-143,-512,390,120,958,-680,-407,-528,-792,902,219,124,600,627,-570,-354,597,307,-472,966,770,-651,580,528,-976,959,386,455,561,-211,-71,-39,535,-337,-592,-26,890,-680,-191,790,740,616,-515,-469,975,-942,299,93,-823,736,107,-525,-179,17,-138,546,-655,-937,667,616,-303,883,570,-354,503,-917,529,-133,-775,-455,641,258,-163,-621,-673,-886,135,11,667,-740,319,-447,-624,594,880,-175,-185,-236,-182,961,594,990,-396,-88,-952,-168,-810,83,841,-355,108,89,-947,-421,433,491,-576,26,950,875,830,-37,365,-374,-74,-24,938,326,-133,-915,520,-830,-569,441,-348,728,870,-491,172,-152,898,-51,53,843,341,-411,958,-417,23,508,100,-649,746,343,-903,-555,-96,-590,669,-577,859,297,265,-505,799,217,-261,560,178,-718,228,-778,472,457,946,-628,883,-934,144,-956,839,868,-352,924,97,416,-622,-810,-496,-957,-665,293,-48,887,-733,-206,993,-417,474,-797,574,653,898,-11,-937,994,122,59,687,-706,-325,130,485,-592,517,465,643,718,-200,-791,-905,-318,-321,-256,-918,-906,-218,423,914,-384,334,-482,813,-193,-751,733,109,33,73,701,-749,400,-405,-723,-152,118,-933,-990,-894,-314,-567,96,-539,-536,412,39,366,-643,366,-675,663,-197,-390,-35,-945,-738,565,-897,-230,230,-208,925,597,735,449,-764,-177,375,-649,-94,-95,-438,-375,579,-260,859,860,-265,-165,198,67,565,903,872,-364,232,361,940,504,101,678,820,-613,-387,296,-530,-709,948,-481,-285,-380,-944,893,758,-811,-14,453,864,-967,503,150,-658,-326,-873,907,-57,683,437,-896,988,680,-640,-251,42,972,927,-166,-491,-695,-708,-119,947,-769,524,-787,440,751,-506,511,486,45,-718,-869,-572,630,-180,910,336,782,-701,-818,-14,57,-449,-150,-499,-785,-581,-26,571,-803,131,-459,231,403,-423,-697,972,806,-536,-638,-402,-816,655,568,544,-885,-646,-336,-308,644,279,412,821,-38,-22,-545,420,917,981,952,-480,-519,-868,-989,-64,417,-184,-171,632,470,730,-624,867,-919,295,-166,987,747,-589,-867,-295,-627,618,231,-160,-507,-716,317,833,-728,450,717,-202,-963,-223,390,-458,-268,783,-960,490,-336,-775,-116,698,344,359,-102,-903,143,-698,604,-117,-87,320,-173,-135,977,408,-677,657,617,242,-456,532,915,-890,-513,-781,701,-472,-344,663,408,102,64,-688,339,-386,141,-283,278,337,-400,428,-934,-454,614,473,114,-536,182,98,98,-908,567,-973,-712,802,-732,355,968,256,-531,608,-512,238,-538,684,269,-821,-914,234,-682,-568,-366,-432,-501,-365,421,-72,537,694,-687,902,594,-500,-664,43,491,-701,-423,744,778,-695,-735,-273,-143,-757,296,-87,-886,-480,-970,748,-827,309,-686,-817,21,-480,623,-533,-744,128,566,-828,547,86,261,974,-852,678,-885,-430,921,-621,885,910,-999,-201,-953,852,321,114,-137,-950,43,-599,351,716,772,-990,434,-734,598,378,364,14,-132,-956,-269,237,479,-471,467,-945,-645,-689,84,-659,-119,736,202,835,576,-77,-127,899,892,77,427,120,-77,774,-954,862,376,388,-20,-957,367,892,934,-998,-814,-15,-520,-402,-656,-801,-794,283,589,-573,634,208,148,-119,-996,-821,-794,-344,616,-142,-353,799,-583,432,20,-242,657,-273,-602,-773,-439,-415,888,-696,-582,-812,-266,-83,-344,-968,948,136,758,-252,-230,593,889,-967,670,391,90,-242,-635,-119,847,512,499,-711,173,487,419,949,782,450,-972,-977,547,722,613,525,688,-33,204,80,598,924,434,-550,54,-449,-458,-356,258,-817,269,-945,-159,-316,930,-59,651,992,-621,-490,-963,-981,-192,358,-850,-919,118,-382,-335,479,951,-205,187,824,381,-898,-204,434,830,-25,-629,-582,905,249,593,-991,394,745,-55,0,771,-293,405,826,-941,-951,944,-313,946,-856,366,264,-875,191,526,265,756,394,419,186,175,933,-710,-813,888,-311,-957,-925,932,-246,934,-856,-469,435,-906,975,-727,104,-290,-129,888,-910,481,898,-338,822,449,863,-613,-922,976,345,-904,616,-965,454,805,-545,24,288,579,926,193,83,-511,-4,611,947,-212,909,-406,374,305,524,-407,-389,257,-91,-868,-497,887,-250,323,295,926,-57,-534,7,-425,573,-599,537,130,-807,-808,-233,656,-664,285,-99,9,648,-733,-925,35,-269,796,695,628,286,-184,526,-50,-800,-240,53,16,-870,934,-384,-452,866,-572,-410,-714,-737,-702,749,18,-768,-59,384,-940,304,-347,396,382,-99,46,418,305,-977,129,110,-304,447,230,955,936,-357,834,-59,-924,416,-520,455,359,-92,11,-983,903,334,-124,383,-915,964,-510,-721,179,233,-967,-171,-604,-210,-781,978,-287,-500,823,-617,951,883,-700,70,466,971,964,627,-252,-845,100,-320,-685,-968,-483,117,610,-457,-6,475,-818,-761,-556,-997,48,-331,-526,-466,-642,820,896,236,646,902,-62,399,83,-2,-98,573,-672,-809,114,972,-770,-415,-674,-960,-477,-769,-825,-686,-93,983,167,-358,-858,506,-504,-50,913,898,-781,-866,-666,263,608,901,-595,-422,-873,-316,466,600,-234,-863,-633,-401,-15,879,-596,200,184,186,-18,-464,-350,464,-450,969,96,-881,-109,-131,-8,218,937,607,724,-728,809,282,-608,-154,428,490,-393,667,-189,-675,-386,-950,-865,-542,474,-117,-328,856,198,-262,857,-600,-143,886,190,-336,130,-901,-192,-479,-564,420,791,-256,-433,308,-957,-721,-46,-136,431,-351,-834,-803,619,-613,281,113,-98,442,-161,348,229,79,-778,666,-431,35,527,866,-433,206,-121,-428,566,597,-887,850,-614,709,-972,-827,-505,897,672,167,-121,-268,-252,-649,463,-163,-452,152,-165,598,-881,826,-421,190,720,-173,625,-820,606,196,587,-5,-325,-520,123,-255,171,-738,-348,106,-474,-581,137,293,993,685,515,-558,222,-938,-556,554,643,-483,995,170,506,777,-345,757,-294,725,-919,-12,-801,-977,-771,-491,283,-95,20,397,-420,-539,-804,-204,616,-959,26,817,240,313,495,-97,243,79,-767,302,0,-244,789,-477,-152,995,149,-639,-444,99,-262,91,183,66,-830,837,39,-283,-486,577,753,145,-770,692,194,581,-542,332,-844,-417,-128,884,555,705,799,837,-394,316,-636,-482,-741,238,64,571,761,-388,-125,-423,141,-552,-504,425,521,530,-825,383,963,859,-610,-136,-709,-886,-945,711,349,-24,-213,374,95,919,-425,838,-342,580,831,-458,612,-996,-277,-765,-130,-923,-717,-886,409,400,-88,466,-968,-593,824,-752,954,620,-724,500,-427,623,843,-785,-74,462,736,-527,-751,110,-485,999,-274,-20,-720,-651,402,-574,-483,-707,296,-831,-59,-449,-638,-61,-995,715,-819,-110,-652,-532,-424,-599,-8,-848,678,-923,789,103,-799,-728,655,-623,-549,786,-264,940,-981,-930,-434,219,143,-810,-373,709,549,-617,-425,332,949,-504,123,-348,37,-382,971,572,427,207,-301,-524,36,2,-895,-396,-527,-73,822,278,326,-931,-400,11,664,-177,641,310,-792,-585,-30,974,-615,499,-297,421,663,840,283,845,293,-718,-694,386,-53,-131,-976,-974,-118,318,764,-999,644,961,-750,-222,812,-437,-572,-582,-891,713,42,219,-256,760,-257,-860,-972,-122,951,351,423,-819,-715,-288,610,-272,561,457,-388,924,-244,232,-378,175,78,-619,812,-85,748,204,-519,870,106,872,771,178,-406,602,971,845,257,188,381,-814,-219,389,381,324,-53,479,212,541,-820,-238,-279,-123,479,881,279,793,94,624,750,-508,620,-700,854,-185,217,835,-714,-670,860,932,456,-397,-771,204,-241,136,239,-638,739,-117,-194,898,-576,-859,-599,112,77,618,-430,799,-738,32,416,-993,-232,-647,830,792,-678,-928,-262,865,289,925,988,989,883,-116,-897,-202,465,-650,-784,-83,-843,-214,406,756,-934,328,-110,345,601,306,-93,90,-237,360,-241,-696,-47,-977,-546,-152,497,-573,449,-993,-527,234,-440,-291,143,-817,-114,399,-36,553,771,-411,-502,-704,-420,943,984,696,572,760,937,859,-349,-685,-867,937,976,-751,-402,-553,311,53,-398,-869,-348,-616,-232,111,681,375,-917,-49,433,453,809,28,856,748,69,759,572,770,248,-144,542,178,714,781,-900,-236,843,930,622,-248,-296,844,194,-215,-415,-246,-818,-802,857,-894,-323,-939,899,802,-114,82,-977,653,476,519,-335,845,-920,-733,505,-915,256,384,-956,-597,201,-473,-9,-92,-708,-147,874,815,726,-587,892,-625,-892,253,367,-726,-708,353,-843,-405,868,-183,-871,-386,-556,233,111,57,49,-309,404,-87,-804,790,-140,-873,981,467,65,324,39,623,-220,954,848,283,-100,-75,-888,-713,-231,-838,-285,590,121,62,460,571,-549,-133,-94,-883,642,-434,-316,-818,503,335,50,-303,-899,-659,-567,-129,270,-499,-164,190,779,532,-161,-490,-555,731,-314,-735,23,-943,835,303,963,-253,772,-282,-168,-789,-415,679,118,-961,-463,992,-560,235,-403,-997,-800,-713,-593,897,-367,377,-662,305,-37,782,893,670,-971,-16,303,144,101,-851,-968,592,-857,859,217,-62,-14,-115,-245,-554,-983,-56,810,367,-846,795,909,552,-156,465,476,776,195,-595,697,-877,-775,188,-653,737,-135,923,-454,-36,-664,984,745,-80,-334,-560,-557,-409,-844,976,-464,530,564,-204,51,-420,-69,-199,-485,500,202,-177,-276,-319,-761,-584,746,864,-248,497,732,-720,200,-637,-530,-806,779,-518,386,-665,-879,594,-303,-503,496,651,702,-121,-984,958,171,937,603,-919,-240,-724,2,-995,604,-586,-92,-235,-744,-848,456,-823,195,467,807,-404,533,990,896,365,327,-857,727,-86,-100,-304,892,160,509,-779,-117,-152,-654,749,-42,328,957,822,-633,48,-226,-184,234,-573,564,-82,21,475,267,169,-505,996,735,-806,-541,609,984,-580,-235,-21,970,-39,-152,545,830,842,-274,-366,-183,-628,-457,992,745,-797,-22,207,-627,320,-988,-783,692,736,723,412,-482,-909,-151,120,-414,-846,773,-446,-482,-116,-382,-869,-756,-746,368,-581,36,70,207,-229,-156,920,454,-112,-306,-184,-536,-176,-4,99,-118,-465,-736,178,644,879,847,-14,-452,302,226,-447,-838,-416,763,-900,24,-454,-270,684,591,821,-5,-584,-333,582,-117,-251,666,184,-489,425,-844,-392,661,-176,259,813,-479,717,851,-188,667,-826,-506,-338,658,-603,-326,710,-414,481,52,506,676,88,169,-383,215,65,-128,-190,531,-935,-127,208,288,648,13,-630,-27,-498,-322,804,97,-254,254,-897,884,568,685,162,-715,610,-437,559,-899,-288,-140,-186,-54,343,-831,687,953,28,427,-108,581,-328,-872,605,846,917,-343,923,954,-181,269,-979,-279,899,513,11,368,369,625,617,-475,-790,-659,996,975,776,787,434,-859,-746,68,761,-506,-250,-712,-411,954,555,-82,482,795,835,998,-598,36,834,236,-53,-286,-934,764,938,-197,680,-914,-197,251,753,124,261,86,887,-892,174,767,482,147,157,520,555,440,-385,-302,986,-499,658,329,-960,276,915,-950,-718,-126,991,-599,-116,629,-289,-850,-522,-63,-185,-137,610,-813,301,757,-297,-316,502,497,-693,154,-966,-672,243,-629,565,586,-309,785,873,-869,907,-395,544,60,834,584,104,589,501,-404,-553,-880,595,549,980,62,-321,-576,-625,889,51,-304,622,493,972,-581,207,120,-996,-851,-448,-913,-751,-115,-152,-831,-946,-950,685,428,-245,842,-672,-706,-266,-319,79,-27,-643,104,-143,-190,514,238,109,-508,81,-735,-38,-578,-555,-864,638,134,145,504,-833,154,399,732,-757,-978,716,217,47,383,-683,379,-132,-220,895,160,-829,-109,-582,348,366,396,443,-859,-372,-417,-602,-446,-889,913,-87,796,-115,-425,-171,484,971,749,348,430,-988,-653,32,809,322,428,-228,384,-841,-469,-992,346,-533,-526,308,608,-778,-408,201,132,743,875,-648,-885,945,-659,-624,-915,-228,669,-117,-671,-748,502,-293,-123,-560,-159,-103,741,410,-493,-883,-123,81,-565,-570,-788,-832,-508,-783,-765,692,253,491,555,689,505,-319,-294,62,-987,-744,-889,746,711,509,572,-977,209,924,-345,980,414,870,524,345,-527,-148,765,976,739,-211,-657,464,-215,-920,-365,408,-419,-6,361,140,93,932,-341,464,-203,-415,-357,199,192,-482,425,828,-159,583,615,267,-999,488,514,824,-776,135,695,397,883,-278,72,402,-296,-385,204,705,287,66,-67,664,914,680,847,465,457,-535,580,-577,-693,651,-595,-515,934,-429,900,-351,421,-121,-18,181,150,679,-616,-517,-151,331,-521,-588,-60,572,692,722,-274,652,-352,-129,-859,-420,-904,672,903,-885,-733,526,312,-850,-968,-438,-632,327,715,-489,446,756,136,228,-536,917,109,425,421,502,-377,255,-504,431,-982,-14,-310,-281,593,584,-338,-50,-812,333,-146,112,387,-895,-467,-542,160,581,-497,-291,-605,143,-115,845,473,134,873,345,-744,390,522,-486,553,-136,-384,-777,-710,-202,-361,-140,-432,487,-51,651,943,-172,131,-987,667,-438,-470,74,715,862,-881,46,341,833,-579,670,-490,39,685,425,-583,38,615,-655,-254,-668,25,-659,363,-32,555,-289,936,751,-751,-46,110,671,876,0,-941,494,581,-518,-700,186,-275,-799,-328,-34,-230,493,-980,-908,-721,-456,348,196,124,253,222,-372,-452,607,-659,273,876,-784,902,-804,838,-116,-250,129,912,733,-638,544,299,-584,-103,861,964,731,-757,-54,-119,-325,426,-617,-240,-314,-113,265,-432,412,745,-329,154,-599,-907,-475,213,-452,371,88,138,666,127,-588,184,259,723,-253,729,-548,-85,416,186,-752,269,-676,156,878,615,-989,527,-45,-995,-482,-240,469,-118,-40,948,-593,405,-515,-270,697,-428,-781,-620,182,194,-730,793,-543,736,339,-552,-343,-126,-167,-403,546,491,125,965,550,490,952,-529,-306,-925,-156,-453,162,-987,807,-257,-634,-915,-242,-47,-122,-431,-769,520,911,-349,207,223,646,-512,-994,182,-553,-343,617,922,-22,-455,-548,-674,-238,239,421,-269,-132,-135,-599,41,-640,-205,-273,826,887,893,-986,-188,639,-322,-488,-336,-989,209,-970,-798,-267,99,346,-226,-215,870,-698,238,-556,-270,-725,-531,67,-926,825,-349,623,-517,-821,735,553,-512,284,522,-658,-213,7,227,-79,8,-536,770,595,-892,331,712,746,233,0,24,461,-503,349,-199,845,702,-548,231,-126,-500,568,-197,-832,895,82,-27,-362,691,-184,310,-952,-661,-338,399,-780,411,22,369,991,-853,-351,-31,915,892,669,-354,-310,-604,-775,973,-144,-478,-629,-375,743,-563,-373,190,-576,-497,920,564,-371,291,-152,-734,-993,-182,841,646,605,771,-223,-706,-334,-313,-424,223,-171,-758,185,130,701,421,-787,-960,105,963,-741,939,-7,457,-48,950,-605,623,280,-12,632,573,812,184,-84,59,779,902,21,103,903,223,-467,601,333,865,348,746,-124,-857,-21,-574,936,897,-379,-845,-108,739,801,-349,-760,579,353,209,-680,109,-882,-322,649,-145,728,699,-238,144,76,851,-370,-892,38,-175,-139,911,-670,-926,539,-395,-85,665,72,-865,412,-138,849,-755,491,-873,166,-326,647,980,-37,-492,98,-842,83,-45,-720,-408,-531,-59,-419,-203,311,-527,-674,703,-546,-14,907,-352,-165,960,-362,963,99,-985,-393,479,171,537,-437,-67,-758,131,178,238,-955,152,-759,461,707,345,946,-973,529,-846,-539,782,-329,108,-480,369,889,763,-394,873,532,-441,-94,561,536,-336,-424,-43,-773,-650,831,-774,573,-394,-266,-615,706,-394,-901,723,-119,-120,-409,883,387,301,-46,636,-410,168,846,404,572,-965,707,532,-534,-759,331,776,-572,-799,336,434,-97,-314,-432,-201,-749,-577,155,-445,387,-575,151,-288,316,812,504,-86,976,659,-177,-366,-558,600,-934,118,871,-805,248,-978,592,-98,970,414,-336,336,579,483,736,119,-474,513,919,-569,424,943,-645,-217,-191,559,579,-690,95,-987,-595,872,-488,529,576,731,76,-584,56,-553,9,519,-885,77,708,-860,494,-147,-764,526,-3,-242,-790,307,896,968,154,-75,-392,211,-963,194,18,-515,-630,674,-778,-716,-989,170,-994,264,-792,162,639,-435,-488,-861,-621,-12,-600,647,-429,-671,152,-148,-263,-482,-823,-933,578,448,-490,409,-416,-262,-535,-856,-716,-444,-349,-908,350,-796,-70,-207,-329,451,-448,499,203,-930,-643,-98,-708,328,679,-679,402,639,188,-592,465,162,-75,-653,662,-770,-568,-161,941,895,-79,99,942,-155,425,-213,-638,-607,797,-325,-885,625,725,896,-367,309,-277,-962,870,-552,-973,-298,207,556,-588,432,-263,999,853,569,-522,626,-677,-180,-720,400,-842,-484,-402,720,-392,995,814,-457,-606,633,569,-16,887,-316,83,778,-722,732,872,464,34,-792,-668,-932,614,-974,-113,593,-53,578,725,269,-945,252,-64,-932,834,244,-74,218,348,-836,691,-63,-324,-888,-197,18,-890,402,-198,-793,-60,735,318,-407,-431,-884,117,-249,267,169,245,107,662,-565,-483,-794,795,-949,605,-277,39,819,-654,634,735,102,279,387,-219,-564,-313,-220,-519,556,-364,-425,968,282,385,-805,-907,328,146,183,-94,-115,-21,-314,413,-219,-506,-287,104,72,529,460,-343,498,-851,-236,-253,-794,-382,894,150,-224,463,-75,-716,690,-325,978,-725,-52,-277,835,-504,583,125,-739,-914,-505,-769,-176,362,446,981,-302,830,965,-183,-69,-278,514,-186,946,-224,244,498,7,73,-948,-978,393,-686,24,-215,-504,-625,-588,997,169,-892,877,-209,-884,496,477,-69,-768,-770,-491,-336,-607,-97,-988,745,-19,-869,998,468,-530,-900,-651,90,-149,86,114,-325,-600,686,-45,6,-951,814,128,994,91,569,524,459,-495,-530,-492,-945,891,684,-365,354,-647,321,692,-862,2,-545,778,143,829,-708,-245,-669,555,-304,-456,400,525,697,687,-787,-52,125,892,-436,-817,934,17,-799,-263,56,401,508,62,-272,640,371,178,591,-971,-650,442,-729,872,733,700,234,453,400,-634,832,-593,575,-230,-721,813,378,-279,849,-823,809,186,411,-469,75,-222,199,55,943,917,750,718,-541,382,-357,-671,52,255,591,405,394,498,389,-989,905,449,-830,609,401,574,694,298,687,-869,691,403,-578,214,-682,-934,-404,280,-865,-928,842,-341,-952,-269,34,-722,-762,-160,-447,-868,339,-133,-456,142,-853,-270,73,-885,931,372,-810,-447,268,211,831,759,237,-9,990,643,427,-957,881,292,-763,-196,711,-982,-847,-872,206,622,-808,-757,265,346,502,857,581,-856,261,293,-213,349,975,-818,-429,-905,834,596,155,-16,192,534,890,-442,655,676,-145,-582,-862,967,-564,-922,-801,199,-92,444,911,-523,180,782,539,-921,-856,110,-260,-275,702,890,452,-458,-154,-916,68,676,331,971,115,-605,-474,-645,-623,473,797,-872,708,987,-113,-397,-384,106,-827,-950,-257,-475,603,-774,659,-872,-45,-472,-33,-666,961,-534,700,157,21,572,558,475,783,947,-817,-727,-568,32,-374,294,-711,-266,-854,67,678,415,842,-251,461,-29,184,515,271,933,-935,-413,-938,422,25,-151,-656,149,803,-10,219,348,-707,545,130,949,-142,-140,777,-318,106,-172,-186,771,742,-298,698,653,-56,547,541,-678,-713,-58,-820,738,-144,-269,669,-856,-784,-999,-858,630,262,-899,46,-188,160,667,92,-135,-321,-15,166,-17,236,274,157,997,-580,236,887,218,-965,395,-902,-59,51,-391,-612,40,924,-537,228,696,781,813,-652,-793,418,107,302,810,870,389,-167,-635,401,762,803,549,-594,153,616,-505,375,216,-32,-45,476,223,-907,-596,-12,733,177,215,-75,554,-897,-944,-911,988,127,-803,-939,-811,-208,69,967,-434,569,809,768,328,-414,28,-262,-409,24,464,691,-26,-993,-880,155,-132,946,730,356,-847,-806,9,-5,349,252,-867,98,-78,-897,609,-304,81,-214,-882,-347,599,-479,821,-22,-4,-998,-415,-978,-707,-555,-91,31,611,-432,604,-702,408,321,-708,-366,-690,-404,-69,-207,-581,60,231,-567,-109,-786,709,-267,-252,190,89,441,-455,-340,58,-588,189,-601,522,374,630,768,-362,384,829,601,-69,-76,-622,527,-54,277,-543,526,-983,-334,-319,851,728,23,-135,-764,-28,-698,-610,960,250,177,430,221,-254,-376,-413,-277,375,611,70,-185,424,-981,258,-13,-123,-999,-713,500,832,-742,237,-387,-740,928,-909,-788,-595,-37,-566,7,138,956,-756,576,-241,755,298,710,801,-153,881,288,228,-86,-654,272,-904,-999,-172,-837,771,501,-23,208,-173,-565,-629,-265,-78,-963,119,-756,376,-661,-534,30,291,141,-137,-535,-875,-750,-298,624,870,-434,-213,-2,-14,-508,-579,872,833,89,394,-338,-513,908,240,-471,877,-315,-322,985,-926,358,-53,-722,-252,-841,138,449,182,7,395,-917,-602,-364,666,-149,-337,878,222,734,-600,-135,-705,-535,-367,900,-219,-993,222,40,-613,416,691,-439,-762,-907,588,502,528,-227,-242,-211,853,-190,-534,442,-479,-374,-374,327,316,836,-218,-568,-942,310,935,98,-452,843,-568,191,878,106,884,872,89,-217,178,-135,-352,461,645,-859,-109,-745,978,739,-411,232,-848,-930,595,-375,-52,642,-125,-584,-427,530,190,-519,-143,-131,720,-800,147,385,-917,860,-984,-326,716,-773,498,-696,-485,965,540,-116,-483,-709,427,257,426,964,567,-117,606,-774,-889,-405,-473,-500,-468,-588,-461,-957,658,304,600,721,-592,-109,-406,-544,-673,-213,-754,-596,-136,-176,-534,86,-133,690,860,580,696,-424,-327,216,473,147,380,-1,-813,942,759,-312,-750,51,96,770,-373,272,-291,468,-405,808,836,-442,691,847,-124,639,-403,-636,399,-208,-7,-281,-672,-610,-84,395,-919,-485,-113,-151,96,753,340,804,803,120,467,655,-424,-55,-642,-271,-910,-614,-435,-888,-443,155,-132,842,962,-844,-753,299,879,-974,128,-691,-935,-299,-502,-340,-49,275,-765,-282,808,860,2,389,207,759,970,-18,360,-930,-645,119,-146,595,16,2,732,703,921,602,-97,-158,268,-913,-759,594,262,-822,-721,-584,-409,322,112,-553,-72,253,-457,-542,872,424,385,182,-891,971,-525,-381,-312,-744,634,132,560,485,115,98,-407,752,114,-221,229,-374,-490,-180,654,496,206,-170,727,523,-596,306,-675,-59,934,275,-469,825,420,-9,124,-870,-814,-292,249,906,-668,-420,-57,-96,-253,-853,-932,988,270,653,-256,272,258,-744,-923,285,727,256,216,-687,715,482,-308,-284,623,-606,517,989,-451,676,-592,803,637,485,66,-862,214,575,-478,206,-679,18,198,-377,206,-67,946,-268,472,129,884,-696,-260,-895,300,-944,694,842,-166,-662,124,-511,749,-323,-960,539,201,313,10,953,152,810,305,-378,-142,-908,713,-144,-400,-270,-344,118,-541,-397,-344,-478,626,852,500,-552,-661,692,-36,818,352,-130,342,-471,-190,491,-228,813,-264,-670,-659,529,997,751,641,304,827,694,-368,-980,-252,-255,598,764,16,958,332,844,-786,809,-603,615,-908,103,559,-299,-1,-908,-405,-231,-44,545,-314,-414,-377,660,729,-468,-336,179,-538,271,636,178,223,-298,436,-1,686,176,-154,-175,380,-54,-257,-890,-254,397,36,-941,300,-872,789,449,-326,-526,735,-216,-804,-152,773,104,-552,-366,679,-985,-232,-442,487,820,-681,653,78,-290,278,-608,-859,-307,-933,797,654,-222,362,627,63,782,559,690,392,620,-16,-129,650,729,233,-152,-186,-990,664,-560,-932,-317,-5,-428,-875,-987,690,-816,335,438,273,269,-429,649,922,815,686,981,911,-607,-812,-589,693,499,45,10,974,325,-534,72,28,-896,-526,-901,-251,202,-231,956,-212,-4,-679,149,278,-206,197,-606,-566,-181,255,-587,166,-930,931,546,-302,443,717,-964,57,437,747,-914,456,-209,201,-210,928,88,166,-381,424,-588,666,665,242,788,-723,-630,958,-203,183,577,311,-769,269,-613,-222,264,-344,-26,539,56,-911,-486,955,173,204,-499,712,730,20,-751,-617,-722,-384,-122,504,241,-676,-279,-554,-114,530,-105,-261,-996,-245,9,379,109,-655,169,-641,-264,704,-703,-353,-546,-273,381,-914,616,619,766,893,896,-854,916,239,225,167,-738,832,-584,187,-121,-203,-200,-134,882,-568,-609,-2,23,-842,861,141,-459,532,-603,332,-931,-77,-515,-269,-856,304,-354,390,642,250,-689,-780,-474,-719,615,-376,-916,-122,-879,-698,-502,-763,615,-119,-905,-529,346,-459,980,110,-635,-684,-378,19,-410,962,-362,975,-238,399,102,-763,-689,-784,322,-353,330,-234,804,-71,415,-900,-324,118,-106,-436,-12,742,462,-156,-156,-421,-453,623,-660,909,-18,396,425,-317,952,-450,-567,-185,-318,520,843,963,366,177,117,-799,287,572,-231,-358,47,141,924,358,-382,-954,-472,867,-839,-233,801,490,-461,-741,-141,156,-567,-679,-32,448,-385,167,445,609,137,-112,-852,-193,-87,-356,-808,661,-12,905,-823,801,-544,-272,722,918,-540,-210,-195,-279,-679,-736,-237,-383,-3,-930,330,509,-384,-142,-234,-204,-491,-62,-482,-34,-274,829,-442,259,-925,-855,-872,109,-79,-107,265,-872,-742,-322,65,-521,918,-170,479,-120,896,26,781,-90,-908,751,-981,549,956,430,33,885,-355,839,418,-566,285,-922,-925,252,-478,763,-939,-483,187,687,-758,143,-527,-92,-619,-882,-948,-902,-545,-678,802,891,825,598,555,61,-269,622,554,231,-443,-944,-726,-909,174,-690,705,-767,-573,423,-185,478,820,924,779,134,-434,536,-806,-320,-945,-593,1,-366,65,-448,-435,130,175,90,-401,856,-510,894,-432,601,306,-249,373,373,951,82,-401,731,306,607,-254,523,36,12,252,-831,860,-19,670,-81,-809,969,144,357,-92,-169,524,-233,-729,33,-342,518,-520,-31,604,621,-606,-124,630,131,225,-537,91,291,441,310,-213,16,-54,-247,-430,577,-314,100,-944,810,118,617,-573,323,663,-150,571,-113,774,853,-314,-998,-615,-149,648,-95,-422,220,-513,-692,-930,438,-247,667,-417,925,-10,-616,548,335,672,420,-925,-939,459,-576,368,436,267,-53,-508,-122,144,93,173,973,-813,-19,-155,704,-614,980,-309,390,887,451,-245,845,679,158,-659,-776,19,-185,-546,425,-902,-291,656,-234,886,-852,-377,842,-268,502,-710,-327,279,-419,-996,486,-848,591,401,550,-14,906,-65,223,-771,-925,107,246,998,-743,38,-160,809,827,-481,59,329,-488,-553,152,724,-888,-594,-505,93,913,-744,795,581,452,-258,767,-382,54,397,-343,-572,-289,-965,474,575,998,238,515,997,278,-954,-282,-524,188,645,-824,-961,-249,-863,772,-977,-252,-845,-419,-437,-181,166,818,-201,93,649,409,-459,-264,-118,-627,180,609,440,-899,-734,-957,-827,572,-110,490,-371,-914,-845,-31,724,-619,6,-728,-574,354,-450,754,-216,-454,-523,-910,97,-284,-109,982,-584,-909,-318,179,-528,-270,76,-772,754,217,-133,725,500,-799,-398,116,836,-253,-587,333,-333,-287,-906,936,940,384,-109,-309,900,409,754,-107,-336,829,395,-796,-428,923,164,-112,-261,-518,-191,339,-777,770,-402,747,892,-340,-44,-769,910,715,-217,632,940,638,-676,-99,-658,587,-782,-903,-998,110,577,-424,82,-782,-135,609,408,185,855,884,204,333,699,-992,586,113,-65,-878,-715,227,818,-813,-154,-27,-770,-336,-907,980,580,-229,-493,458,835,794,-53,700,-630,833,398,618,-448,-672,254,450,-723,662,172,746,-864,-616,953,-724,-257,244,579,-863,-451,278,179,306,448,-77,143,314,573,-231,835,995,-274,741,-50,747,281,-997,-83,45,-842,722,-942,-240,-335,289,278,849,517,-900,563,434,-769,-829,372,629,573,670,-122,382,617,-88,34,592,416,394,939,-652,-503,-490,-615,-62,150,603,472,415,-202,615,-523,-708,732,-558,-856,930,-654,-465,-5,456,809,-512,119,-752,927,579,-106,-900,-540,875,682,-835,654,577,725,126,-700,-149,340,799,212,-870,736,-6,715,621,-424,128,-160,249,-518,848,-762,681,-230,-748,695,77,307,-501,273,432,588,232,191,781,-3,954,892,-963,-43,-63,619,864,-844,-318,-763,756,-51,138,-81,-936,-886,401,289,537,-539,7,-179,651,94,388,-314,863,-717,762,-423,-381,961,110,-519,866,-852,648,591,-316,283,-401,-293,-957,-929,523,-768,33,781,690,-667,835,-677,-490,438,803,-561,58,268,578,-125,414,-775,-667,-494,-466,272,116,835,319,942,28,43,907,936,-940,363,-58,607,948,-922,-486,117,735,-615,-480,-369,-425,-469,16,331,844,-733,-557,-513,-334,-661,879,496,-903,796,951,-328,-802,-33,741,794,144,-895,880,-378,-844,158,-523,-889,-102,-17,-393,-487,752,347,589,165,-844,-244,383,-179,-105,931,-92,144,285,-826,508,-242,323,870,-838,670,-426,141,17,360,-672,640,-513,-479,-960,795,-98,-831,-656,-375,596,906,677,-151,-569,274,-370,-205,-511,-379,519,-17,-368,900,191,-19,-743,893,-292,857,-380,-853,226,-223,-571,179,387,-73,-767,-255,341,250,361,194,758,214,531,-231,426,-977,-999,775,247,-341,-472,737,-384,387,328,76,-76,-966,-44,844,-68,814,233,-145,465,712,764,886,974,574,-615,-945,-955,-121,758,126,321,559,-1,-93,-156,-566,-557,514,430,-705,-39,339,-962,516,517,-176,843,-345,508,531,721,-82,-630,-123,80,-476,434,-863,497,-463,465,627,-897,-952,-922,134,-612,-216,860,782,675,-703,-392,836,264,886,478,506,-582,-712,769,57,-439,-211,-556,-627,-761,-642,744,686,29,-170,-604,-505,-420,-946,882,-903,62,-443,332,-597,-642,-326,233,-116,942,-602,-431,795,-567,450,-529,-901,-198,-841,-1000,214,-814,977,779,-331,8,72,-85,932,885,-348,766,-938,4,873,-540,689,-99,134,762,-589,-535,508,-845,-385,-20,-983,178,620,-589,-871,-722,269,376,-328,835,261,321,196,83,-320,-685,487,462,-418,873,-336,567,-672,824,-320,-955,403,779,203,82,-628,395,-585,600,-730,211,-918,546,-580,725,524,145,-488,-674,208,8,510,-782,-985,751,-530,737,127,-497,-587,533,-411,648,-168,-571,-638,321,-20,-71,-692,402,655,-301,-214,161,228,763,-118,-39,-734,-519,-516,801,-787,-240,259,725,611,914,291,825,771,-573,182,-340,-790,346,-974,-850,842,817,-427,-402,844,218,27,-988,749,-434,903,33,638,815,-532,220,-633,94,396,986,-4,752,613,640,719,214,-794,-359,-814,464,-551,816,36,-104,442,414,419,157,-14,681,-322,243,326,-259,416,-901,512,242,-660,-471,-228,-981,658,51,83,-867,166,-694,442,-63,745,-38,282,-745,-836,124,-890,562,320,897,291,990,495,886,-308,-11,-299,-24,821,407,-341,-150,229,199,209,-116,471,-47,-279,-64,-279,-314,610,910,-347,-669,10,292,379,177,817,-782,461,-231,-213,-653,-192,294,-611,-196,916,-282,-650,382,-824,8,852,-712,-451,-107,312,-60,-407,369,-457,201,297,-295,900,835,-293,-167,-387,-721,-217,167,-420,852,408,825,-320,885,-598,230,-372,92,-757,-230,815,-280,-422,-248,-137,767,-43,491,-3,121,499,789,595,981,-330,-72,-580,-292,657,-639,-382,647,-620,-189,-367,-208,223,151,-961,94,185,-534,79,-188,-508,501,200,409,607,-856,637,960,630,-563,263,-541,484,581,170,672,520,884,893,468,450,265,781,-473,874,-507,-662,352,213,947,929,149,169,952,-200,-492,677,-175,473,-655,-584,-544,527,550,467,588,270,56,-195,414,923,956,-696,-684,224,-593,409,-870,-79,353,-164,-114,-310,176,-639,-214,-586,467,427,509,-347,-985,-820,594,977,598,-874,920,11,222,737,112,-567,-817,-534,-944,905,-272,-832,-525,620,-468,816,-859,-901,30,-778,-94,-59,-602,-999,141,-560,-76,645,917,519,-923,716,-90,811,-750,-46,-316,-82,-352,-957,-489,654,-761,-417,118,2,-716,802,182,-351,-603,-753,15,114,-352,207,845,602,893,501,718,406,42,-504,770,847,-108,974,-672,867,94,695,277,767,-43,-747,409,393,-249,572,-856,236,-608,588,528,-89,781,-76,515,112,907,-150,-94,433,-314,863,-313,-296,-867,296,87,-195,-961,409,-43,-866,845,-797,-481,437,-898,-120,-913,739,-397,-984,-223,-870,-765,-430,339,-616,246,297,114,-650,-434,928,-724,998,-413,579,-916,-756,536,491,777,-481,-997,498,-854,304,-552,759,-253,-829,-342,-773,904,-370,-522,-845,-744,60,-512,-772,-190,227,-876,-226,379,-207,-31,764,649,-859,184,84,486,-448,593,-926,-596,-611,-349,169,526,627,-639,-882,290,326,-620,452,131,599,90,127,-27,-635,-149,-22,225,66,-303,-547,-313,-679,895,660,-808,-313,-850,-261,-322,620,-11,203,182,-199,-932,935,355,-254,-892,66,910,-848,333,495,480,80,88,-901,63,179,536,117,-625,-649,-367,878,104,-444,-281,384,-211,57,933,724,-189,130,306,868,-666,626,467,925,882,-71,-337,-571,627,-955,469,-865,85,-877,-355,107,37,-745,-269,360,-431,226,-788,-438,-676,52,-144,374,319,58,-112,-588,7,784,-510,662,-473,551,-197,-869,807,951,415,779,199,-590,-230,111,387,817,921,179,-192,109,-742,-35,615,-646,-825,-76,77,413,-229,-252,-749,884,909,-422,-584,477,-662,-370,763,68,391,271,288,613,404,-151,668,496,251,-441,-543,401,25,-639,490,-640,-641,-95,-917,-325,817,611,-166,-848,-933,155,231,763,-99,498,-392,-836,-654,983,675,-26,647,-994,175,-344,458,-586,-670,909,-205,268,-66,439,138,-888,284,-940,482,47,69,-702,-47,-116,688,-837,681,-906,-153,-474,15,-589,-20,415,975,94,758,982,-908,87,871,-767,-410,327,-51,963,-66,649,-770,29,241,-216,995,515,-830,-142,923,-512,240,991,-59,-214,-73,-247,446,2,178,251,903,-401,491,-33,-301,-734,-317,975,349,-127,70,-203,-122,42,-162,-727,-772,705,252,765,513,-838,-197,-208,-389,-149,636,482,-131,-723,-43,973,-918,-784,463,-987,-528,-871,684,577,351,434,-98,649,840,-459,811,310,100,204,605,-290,-545,586,-356,-420,-170,-816,-980,905,325,-570,210,-822,142,354,452,693,724,19,311,792,-612,882,363,-905,160,-918,-806,-999,-505,-573,-990,-635,-809,657,-162,-954,-179,310,723,44,-403,-885,631,415,81,-711,-286,826,601,-362,-413,-324,-977,79,600,-682,12,443,816,-91,-147,-21,630,-796,311,-808,-597,-283,957,773,302,236,-216,99,31,-318,352,-201,420,372,-515,28,-490,828,-678,883,-682,258,810,-59,119,226,27,-860,-855,-474,-239,774,821,-417,-26,379,98,838,-700,174,-73,-109,-109,966,748,421,-92,69,-152,-47,-356,-712,756,386,-263,-372,-222,-62,188,980,-298,734,-124,902,-136,741,-311,-606,348,-391,-461,-546,-2,-30,-412,739,640,75,718,-125,-884,820,-687,-549,942,937,-1000,518,-314,201,99,981,510,82,574,348,652,545,-692,-133,909,47,802,450,-205,-841,-342,821,192,769,59,-884,-881,-535,-863,-624,-693,876,-445,-896,76,856,31,-35,-904,-832,859,617,424,224,182,-776,805,54,257,466,759,-567,-263,-361,215,-580,372,7,622,238,917,-395,790,-295,-613,469,-444,698,-413,743,-738,655,-752,-673,44,4,-387,-231,-840,-371,476,-354,831,-89,-329,-757,-618,393,-552,-102,571,637,523,29,-320,472,-366,660,216,-56,327,307,452,872,524,-712,-880,355,-673,-274,790,741,-690,-731,653,-345,-559,-912,306,-373,-76,-666,979,-458,-778,170,-66,-110,874,-127,-843,-299,-131,-817,522,-422,785,-741,-234,-342,-505,-429,552,362,-793,413,20,354,484,837,-165,647,-367,552,923,-903,-799,143,-302,354,4,52,665,-176,875,632,-711,-982,257,-547,972,399,901,-511,-970,-319,-976,-428,-116,892,683,496,912,-319,-313,940,-207,-373,-421,899,136,584,-441,-986,239,-541,555,391,-105,-530,115,857,-278,-870,-785,151,-600,-960,-956,499,786,630,811,-119,-483,-618,-297,856,-720,-210,826,-63,-705,-876,-447,633,-794,-271,-268,538,-556,995,-167,328,248,51,912,939,-502,-458,-927,-762,-919,10,-963,424,950,462,393,695,241,-829,-209,-971,-867,-307,-957,107,-225,197,986,-11,204,-619,-310,-640,744,-559,-195,40,887,879,638,443,495,-610,-927,914,459,-879,-34,743,-105,-777,-611,820,537,588,-823,-901,469,436,-938,-700,-656,-378,-818,-721,-332,949,-997,-164,-347,-591,459,-178,-174,-419,591,622,-599,-478,896,409,-844,358,395,912,641,-181,824,-727,-936,161,-416,-516,-299,67,-395,-227,-518,-181,345,72,-699,-27,715,688,188,516,-234,-396,-754,717,824,-473,541,-790,-483,212,-281,8,315,226,-165,964,-3,166,198,-616,-342,960,219,739,971,-671,-958,825,-398,178,293,877,839,652,128,473,-873,-414,223,982,964,-585,201,418,-884,-130,184,-109,800,326,-792,-200,-873,-270,12,458,551,323,137,-41,-188,-954,-749,-125,-629,-862,-647,-433,374,-570,866,879,-438,-511,171,-4,-192,-125,282,-681,625,49,124,617,280,-633,170,-355,912,728,-337,153,115,-691,694,495,764,652,-936,-131,466,-678,-826,-122,521,-386,-839,982,-150,-187,-62,-912,522,-248,-254,694,-928,432,-584,844,897,-288,195,-849,524,-114,-614,-957,991,-469,618,9,-286,-214,-419,-576,865,-96,-567,617,-352,-319,227,954,109,-709,507,-821,366,-623,235,-485,-231,-690,-484,-750,137,-515,361,945,413,928,115,-490,796,-79,-432,364,-222,-682,185,-718,-296,-869,752,-433,511,-788,736,-647,-242,-57,127,-353,64,198,-108,-80,850,602,999,-829,-977,212,612,-159,564,608,-632,336,332,789,540,-125,-556,971,873,-705,601,326,-557,312,-988,-66,805,575,798,-464,264,298,-819,-785,-610,-908,570,294,-634,176,-734,-824,858,990,-688,-205,831,-728,-386,-910,111,553,375,-980,26,212,474,-86,755,585,371,619,892,-202,938,387,-171,-101,109,-90,-29,-984,-864,798,67,409,813,320,-587,-993,-46,325,-500,583,-395,366,819,-533,-433,-573,973,-589,957,873,-732,-50,775,-251,355,383,-531,-140,975,-698,495,650,238,-963,454,978,-613,-440,-790,688,339,740,196,-562,440,882,-462,-833,880,560,-528,468,291,-330,-654,198,988,171,854,175,-985,-629,-922,-906,394,421,905,242,-990,214,372,998,761,-740,220,960,388,350,-104,347,351,212,694,416,443,95,152,-927,-51,985,-826,-379,-261,409,250,-202,-452,251,-792,90,857,-732,110,-442,-520,231,-318,616,384,168,-282,-402,-975,-699,-695,80,513,13,-966,-517,137,-580,-41,-926,566,-158,-595,601,774,87,123,536,205,-401,104,174,625,390,789,-101,843,-271,-126,-556,361,952,346,-409,-39,-215,462,-293,255,16,679,-223,-912,211,419,-525,264,787,752,801,-789,-700,265,-143,805,-657,-26,-93,78,-487,-474,75,-228,422,192,140,-79,-866,-864,-370,-27,369,-60,-886,455,195,-185,-251,-154,471,856,695,935,-147,291,-637,204,941,538,382,885,109,194,-501,-97,941,880,456,-159,-543,-118,-745,899,267,-486,-964,722,-763,953,600,236,924,644,-855,-8,-376,987,-532,-457,-787,854,659,646,214,322,-263,245,-324,840,468,-752,803,-642,-493,710,-78,-414,-215,545,17,-942,796,-659,28,788,894,-625,-321,825,-229,-923,-586,-210,29,-71,-104,577,-144,549,-530,-495,672,197,-529,918,-246,-548,159,-148,-298,-82,-474,-134,306,622,927,109,-129,360,-160,688,587,-644,-677,219,750,994,-171,741,511,204,65,-46,-350,449,86,212,802,-204,931,-961,-151,-695,1,-101,-122,532,-300,-404,-610,851,-313,572,842,-742,-717,-297,-722,137,-285,883,377,-722,0,255,-403,511,-828,94,680,-729,100,-555,-229,176,-575,420,-1000,391,207,-334,157,648,-361,-809,91,911,-215,829,534,756,-899,763,-99,371,451,531,86,-451,204,75,-435,134,609,-322,-701,-696,694,-178,-516,-712,-696,787,988,844,-798,181,841,-930,-526,201,507,335,-819,-751,-170,563,123,114,-255,-277,595,718,-512,-386,-510,465,855,-146,-972,-919,669,238,293,-168,-151,939,252,885,473,-873,-578,-548,196,-16,-748,130,169,-174,463,755,907,-857,-983,-933,-438,-212,136,-695,-703,617,614,460,-513,-983,-685,-65,183,-680,358,977,-21,463,276,664,-238,998,914,-651,-591,-457,851,378,584,-276,-341,-428,-890,-835,855,-893,-582,-725,534,594,-403,263,124,-936,-237,-689,-968,388,843,415,316,-291,322,778,-325,821,-112,-968,264,-883,267,-350,941,715,-368,752,285,888,-545,946,608,-220,388,245,70,-575,-870,608,-872,881,860,80,823,-888,747,547,897,67,-172,97,-697,-228,-376,611,295,-755,-756,-374,67,153,-958,187,-419,979,413,385,240,340,-246,-128,-538,-670,-288,-987,-517,-800,-823,-863,257,642,-530,-549,353,-636,-533,-825,-919,-506,-592,842,528,989,958,613,-408,-380,-286,751,825,19,-726,807,-442,-238,-257,-367,-729,-91,-624,-233,-213,-741,267,-475,710,-453,65,-885,-570,-540,105,-205,-1000,100,727,-478,748,712,-465,524,708,-974,-105,-99,-990,-695,75,-208,-857,-337,375,345,889,361,546,-505,-740,-60,785,-140,-274,-767,-334,195,774,-881,659,-61,31,437,-752,317,-165,-774,383,584,-15,-793,969,-7,-631,-307,-543,-661,-216,93,-564,12,-287,333,122,267,-892,-272,-471,774,784,393,-84,849,909,-266,-777,-129,119,527,651,292,-236,334,-312,-70,283,-587,-998,496,-964,-349,-986,564,-303,-244,317,-200,-361,-759,182,679,-563,494,-786,786,362,639,468,-197,229,794,-471,-717,-549,359,881,-89,621,-874,301,994,231,-7,517,101,-750,-473,-379,-498,-916,586,102,-960,303,440,446,419,42,159,519,784,152,934,963,668,-732,-185,513,-423,209,175,180,-886,353,516,-99,791,176,145,993,-876,14,-141,-267,-488,-191,-835,205,606,-959,-166,288,-523,986,829,-615,95,-861,-67,109,-511,-837,922,44,133,-622,-760,791,958,-702,-779,554,105,30,775,-104,-722,212,-660,-345,456,321,-580,-469,881,-993,-161,-536,591,-844,-557,-138,332,-612,21,-950,36,-53,898,-702,689,-416,694,-534,370,898,449,-210,570,-121,-889,915,980,-607,-258,167,-57,956,232,539,12,861,774,323,917,27,729,282,-766,494,484,-783,169,-427,871,346,-87,-405,639,-482,488,884,-95,-774,-245,-154,-944,-846,-557,-663,-975,-580,581,865,780,825,-856,-783,-757,-439,919,-127,-971,343,803,706,-937,-173,-274,-448,-865,94,655,-274,-359,-853,-748,909,-888,82,-427,31,-722,28,880,941,273,-162,-487,-572,-320,-75,-551,-60,-755,507,224,-968,777,285,12,75,-524,778,989,-882,62,-193,768,-785,-870,335,211,-947,-519,544,-307,629,25,701,-918,768,-409,616,-716,536,-416,-332,-349,-302,-851,-60,797,-90,713,417,321,-750,-722,-551,190,-502,457,-501,-327,37,958,56,807,-503,588,-231,-52,824,166,-546,-143,133,-964,985,850,-225,-599,-686,935,-250,922,75,-863,-232,947,-53,397,795,357,864,-49,28,393,753,-702,-592,-427,-876,-531,-941,603,-552,72,463,486,329,-706,399,-921,710,-498,870,-311,90,12,-601,-405,-219,-485,-841,101,-649,-958,-879,-738,-799,-789,488,-196,406,190,-475,-178,34,508,-859,-68,370,514,399,657,920,-918,923,760,-820,-713,-879,-451,-25,729,-481,-506,-476,78,159,-800,-211,602,-212,245,-543,231,464,-84,-734,-566,425,-671,-33,-483,162,-160,978,-840,588,-746,926,409,-598,753,-740,-482,-54,-461,272,-916,805,-448,-868,-65,-878,343,909,723,-811,662,-15,-731,-690,199,-229,846,-781,-28,-67,-655,-9,784,-591,224,-315,865,-54,12,575,673,-298,-877,497,-288,-881,403,-878,-802,896,281,530,83,567,-910,-879,966,-831,914,60,-815,315,776,-812,58,-827,-290,-784,-689,440,990,-367,250,-979,-621,-599,-114,587,906,232,982,-467,-636,635,-241,-882,-941,712,919,-903,82,-573,-458,650,-620,-414,-355,666,-992,723,87,611,101,487,-682,-87,-618,743,83,856,185,968,147,634,-901,-171,536,-809,22,-361,718,485,-57,542,971,-984,-110,312,766,527,-220,929,637,825,-45,-838,-921,278,-458,-314,938,900,-731,-115,575,-156,-351,212,-287,810,-481,867,-914,-800,-693,-672,-785,637,181,37,-97,485,933,819,167,-126,-587,365,507,-191,-694,-182,521,518,-733,-650,700,145,-886,-733,-91,-915,-363,-513,-502,798,-193,220,753,-88,988,-936,-557,-36,113,-942,-405,-263,-100,-622,-924,638,-567,-150,-957,413,-569,-411,855,-863,-652,-65,-943,-822,300,508,886,202,-195,756,-272,-927,938,134,-966,-647,606,-89,747,-493,361,989,695,-57,-387,-775,-167,827,-759,-256,-688,-618,68,-919,-316,-374,701,-366,225,971,-652,395,452,-268,223,497,717,179,615,835,-353,-543,921,310,-607,-998,-577,-640,-4,-735,-95,819,-981,-221,496,427,-428,-720,-222,-57,-91,295,237,631,918,470,357,379,807,-250,757,850,-19,500,294,994,-621,-656,-686,424,-656,-476,543,550,205,493,388,471,-335,-80,577,49,-843,38,540,49,539,478,-662,18,-594,-79,769,-248,846,-377,-230,-78,895,855,-345,-675,-360,928,86,7,560,540,-363,785,-78,780,271,-665,-806,400,-762,-514,899,-142,-987,282,-679,445,657,563,688,-149,439,245,678,706,-644,-818,-800,-795,-173,420,-514,-316,569,825,-450,908,437,808,-876,-832,-51,522,-28,152,-655,-879,536,327,-323,-930,831,-123,-563,-423,483,-313,267,-963,-971,-97,310,778,818,-880,-587,583,-243,-856,-849,472,621,525,-664,-976,-688,42,12,414,-9,-634,-768,-940,-50,48,411,-576,91,533,94,-920,733,-966,-699,-573,-598,-971,-864,851,632,-49,-352,296,131,-407,-961,-236,-327,-429,193,-839,457,974,324,677,-671,-588,-154,-342,-543,293,194,903,384,-489,657,-163,713,-339,-361,555,849,-810,161,499,-239,-415,-23,222,890,-160,-727,-720,617,796,-911,981,-982,-163,-862,-989,547,-46,-424,-803,37,57,-835,270,-224,-778,900,-589,689,748,724,-278,639,-786,330,593,489,-605,-650,-733,-923,139,-750,668,219,-625,569,499,103,-513,-905,-580,-594,-940,-894,474,-110,-422,702,-363,-150,-634,-263,521,-75,147,794,684,-530,361,-904,-901,-484,719,-729,501,57,339,-447,43,126,332,851,355,-450,-369,-716,190,941,197,46,732,-448,917,890,-726,274,159,809,-901,995,-186,656,-195,180,-94,-132,434,333,-372,-539,918,149,-619,-603,80,-224,-311,853,864,593,-844,-660,736,-1000,-547,64,356,-678,672,273,-511,-348,134,715,-762,-454,-358,675,-493,-556,800,-621,-932,563,341,715,-993,-223,981,-677,-734,62,831,-192,726,-593,998,-645,-966,-772,-602,-843,-77,-313,256,337,650,-670,825,785,687,787,-50,-432,799,-681,-478,520,-280,654,-446,-926,286,-460,519,-408,-114,124,481,122,-495,83,984,779,396,-661,696,571,274,-197,848,-69,-405,746,-802,320,31,145,-224,-365,-948,651,-277,116,585,705,345,-173,883,-865,11,173,994,-631,449,-978,-139,944,485,-806,-361,-684,-858,679,-621,-435,-455,926,-695,-13,-984,175,-619,297,578,506,62,-79,749,517,347,504,33,-967,-168,-720,-326,-143,514,237,69,-470,702,-116,98,-116,-200,-745,-956,-517,-62,-573,-293,-101,939,645,-913,898,758,-488,938,419,208,452,-215,-282,672,481,-674,707,-526,-901,634,156,879,-113,-882,-606,381,-435,578,-234,222,-140,376,-328,306,-557,956,169,773,-855,612,905,-693,986,-23,-884,-188,898,-799,-249,496,262,-10,838,-27,814,726,260,574,793,145,869,283,-931,-918,812,712,753,-464,153,117,-145,-179,-722,260,661,235,-586,-468,-892,-822,-730,75,237,840,-921,318,-135,-259,-802,369,-18,387,-117,-106,-902,-18,981,491,-705,889,768,181,-427,688,-545,713,733,128,-978,-475,839,-33,826,-354,87,782,-110,-363,977,926,-848,968,-750,242,606,666,-881,340,-46,-99,-449,-753,-240,-598,89,674,-705,1,533,-766,-276,-501,390,-512,379,-170,-689,996,826,-755,892,-58,-555,-632,-369,987,438,911,566,383,124,-2,42,-608,-948,794,145,454,520,780,-249,843,-362,-695,146,-433,511,637,-49,-753,-912,902,357,392,550,-32,941,117,838,198,188,52,608,-39,-28,-574,-572,-75,-16,-583,569,-736,142,539,439,-893,-669,-406,352,333,254,-823,129,-999,346,-781,-128,150,50,231,-925,-822,471,-252,-860,606,-974,-954,436,740,827,-381,-565,-239,-841,-967,-99,-5,-617,-443,465,-851,-992,525,555,398,677,576,-978,-378,-710,-49,143,-11,136,-867,557,981,-36,24,-13,310,-759,-369,-500,88,-790,-153,-299,-360,716,180,609,-836,605,-984,-458,-555,-63,963,542,-454,901,945,-42,-502,343,579,82,399,513,-853,-371,204,783,446,-303,843,22,-787,-398,923,-134,38,-907,197,-166,-267,-133,-362,266,-743,888,434,558,-139,810,735,458,623,189,193,-97,-640,-924,-111,789,-9,-878,-94,228,827,44,-434,238,-886,982,883,-79,-448,466,724,538,-112,526,-1000,-916,401,841,-611,329,-826,-995,651,-406,-778,728,676,658,-956,68,740,377,-484,-958,-786,781,-299,-845,-560,-429,-461,124,375,12,307,-554,-89,952,861,772,22,762,429,-257,574,-729,-289,-168,298,426,-350,-172,452,-909,852,-229,-323,-143,229,-486,110,-446,-515,110,950,865,-971,282,-738,-10,-731,-137,337,-747,-825,-234,-615,566,-269,-631,-840,-960,850,567,-101,89,301,891,-148,87,-725,-795,-166,415,-9,-241,-828,-402,-571,338,507,-488,14,-354,0,523,-882,786,653,569,581,-224,-548,491,-340,-770,764,-23,676,956,-802,345,459,113,794,-688,-141,-241,456,796,-247,-959,-657,-228,44,681,-578,-411,356,-410,431,407,-679,681,-968,677,119,-218,-433,789,516,-231,995,-361,354,776,-769,-14,503,-39,711,607,784,-702,300,317,-842,-829,278,-939,312,-225,178,363,-884,320,-187,-776,-557,-563,911,-179,-6,899,-805,-510,9,392,-231,-881,712,709,-162,-836,-877,-552,649,-135,-431,-911,400,346,270,-585,762,-102,580,-537,-431,304,562,640,541,306,-248,32,776,-766,-396,935,419,-758,343,987,-546,-372,-236,-241,-752,-993,365,-689,726,166,595,-907,872,128,9,-353,372,-499,600,20,-545,-285,-163,-142,170,-56,-496,-810,696,-137,-142,722,151,-348,221,267,-499,-419,876,336,622,-850,-154,144,-240,949,942,288,984,384,-417,424,238,-686,-69,841,973,-83,-182,217,-193,583,-890,54,-868,612,974,107,841,-141,-34,844,-952,440,593,-154,985,838,-503,408,796,-248,162,208,486,234,398,279,889,-123,916,881,-627,638,914,-775,110,901,-977,67,702,269,-70,895,201,-563,357,901,838,-506,-343,820,237,847,-34,-644,310,-123,-572,-1,461,138,337,-380,235,-342,-15,836,598,-963,182,270,-595,-495,-333,211,547,-689,-450,-977,852,327,659,-412,277,856,321,634,-973,-768,-907,-526,-147,180,-304,589,973,-414,799,-26,639,14,764,-929,787,126,-494,173,194,239,-757,37,868,958,945,-83,-560,105,110,891,628,-639,-987,-403,83,-95,634,573,278,273,-191,-843,759,-648,158,934,669,-992,-322,124,-660,267,544,535,-344,607,-197,-655,845,-764,549,-284,502,-602,-924,-333,146,-389,977,-721,54,-606,-533,158,-98,261,-411,-354,98,-86,-892,-821,-878,499,482,-406,165,-756,-976,-584,-576,-605,-268,-783,-268,767,860,909,493,612,-793,-978,-64,878,619,119,939,-665,230,464,164,269,914,-957,314,332,113,174,618,-736,-361,-851,339,902,-634,-102,68,96,249,-189,-269,636,-641,204,409,231,862,258,668,-47,-1000,-660,153,-540,-457,700,162,377,16,-624,-761,-909,191,-929,-181,399,386,307,780,501,-540,-481,-524,-970,-340,-754,-895,-441,-388,692,923,506,-608,857,-900,191,263,773,580,-613,955,385,-351,351,787,-619,-553,387,-235,998,726,-349,809,145,-182,-726,598,136,738,788,-356,430,-797,89,430,-564,-861,780,-788,-615,-900,-581,-386,94,953,613,-468,264,-578,-146,-974,-104,69,677,-925,661,13,-678,4,-132,729,-953,-520,743,-159,270,-589,-290,-318,901,-762,677,85,-234,-687,299,508,202,828,-422,492,328,-538,988,512,845,-968,233,-480,704,-8,-146,36,599,-953,232,762,702,835,-494,813,288,-484,835,-302,-241,-379,767,740,620,21,943,-418,-666,566,-826,-332,-341,-34,815,303,-93,935,-434,-859,-932,358,-847,247,-882,403,161,427,271,-246,-673,-388,-189,667,-902,-430,526,813,457,867,-489,714,595,-651,368,-300,-684,367,-627,417,-151,-950,175,752,3,-463,-59,533,-329,331,189,867,146,-986,769,532,804,-618,692,759,-263,-739,408,-699,-856,645,-77,-119,-124,-418,-773,-998,-423,188,-390,-851,-830,-257,737,-80,-373,843,-953,-119,-217,128,542,-41,295,680,794,-78,303,-286,-515,-649,-193,-139,645,351,528,559,580,813,-275,186,-660,-771,-576,132,613,-208,-32,-64,-912,-670,-621,-344,827,-745,-127,-41,631,257,-657,-423,967,287,-603,-730,973,-319,-462,-807,360,-253,-14,-304,114,100,-579,-160,718,868,510,473,31,-646,-204,-444,185,-473,134,318,914,-291,-522,-551,163,-338,-498,554,749,934,179,-125,-99,917,-621,-156,-442,52,611,-411,-506,-201,17,685,-814,609,968,658,-418,-655,856,-456,850,-683,667,-814,43,547,-49,-778,-447,38,-43,-725,130,-815,-878,-103,-824,182,-735,-604,-743,371,123,804,810,-465,-10,371,92,-878,761,840,-388,279,-345,-232,-443,894,438,-930,-686,-754,-137,-142,-658,-336,932,83,80,200,859,-265,543,797,-649,207,603,671,-244,-319,632,721,600,411,-714,131,-823,-67,886,-294,-635,553,-586,-417,43,-240,372,314,-18,-758,897,92,187,-404,-890,307,769,-141,-205,545,-784,139,531,-323,303,799,-847,-419,-204,491,774,-230,-154,54,-522,908,-440,382,-882,613,-977,71,-383,-816,-486,602,-235,840,-507,82,-427,-196,670,-247,912,-962,-575,-440,349,-811,25,-128,-323,-946,-664,-521,913,252,-861,-733,369,-158,-14,-224,-587,416,339,-66,479,-104,171,795,-680,291,-938,-889,-885,354,-153,-685,-107,-242,256,227,-697,-993,-992,572,591,808,514,497,-79,-597,-414,763,-878,-619,890,256,607,-441,-83,-417,32,-269,868,-388,-471,-79,-906,-538,-503,653,652,-864,-795,-243,503,-301,525,639,-314,876,-699,-457,67,787,-136,802,-347,-511,-967,-12,-968,-94,-248,-714,-310,-531,-305,795,-510,-418,-108,826,711,551,-998,991,-81,-279,149,459,-910,-363,-1000,497,-881,-290,446,927,-991,-766,659,-90,883,-713,925,489,-232,-599,235,-825,-330,-592,-822,89,-990,640,621,632,-313,374,-95,-63,544,-196,812,104,-225,-13,-364,529,-762,124,-448,665,-454,-300,304,-516,-462,303,773,876,-338,145,329,880,-622,535,-365,743,163,-823,474,940,285,700,551,786,983,-774,353,216,158,495,470,-841,-100,-664,0,-485,887,385,-626,112,-430,-396,-838,300,307,-765,198,136,-619,784,-187,682,-577,-254,358,-604,-664,-773,-378,-172,215,251,997,481,-291,999,776,-685,453,599,-476,988,-16,-355,-704,406,-850,-376,-315,123,-840,-228,632,896,-966,531,766,713,725,838,-345,-994,-777,-732,983,536,620,757,-652,-19,-808,854,980,-66,492,-570,-913,237,-175,398,-266,-489,-117,911,-380,-940,417,184,464,-70,-653,246,54,776,552,-594,336,975,134,534,-610,-866,-353,-860,-568,597,499,85,-47,531,-732,152,324,-360,-767,487,-956,-743,526,-248,523,446,766,479,527,997,931,918,464,321,-539,157,550,469,-873,154,476,153,-855,950,-88,-781,547,357,192,-464,-198,-756,445,-488,748,-232,676,-608,-376,729,-456,-422,194,735,-881,-146,436,-942,-425,-879,-533,-656,-712,-154,449,-179,-748,204,188,-469,344,-530,704,-235,-893,596,404,602,302,619,-635,876,68,-938,611,-679,-931,147,572,745,-177,-486,911,-538,-614,-450,-581,-584,309,-880,758,-224,576,319,289,-938,-165,-54,882,226,940,-975,-398,801,-601,-537,223,655,-455,-824,609,275,-310,-29,730,-386,-555,-267,-328,105,598,841,434,-729,996,-995,-249,239,713,408,513,-579,-922,815,-214,308,651,-918,-608,337,-13,613,-579,117,374,339,-635,-221,-105,-341,-710,976,-918,-741,579,-383,-330,-977,-354,275,-452,-830,-584,-680,441,-52,792,-289,983,-25,145,950,612,-657,-682,869,114,-500,-838,1,-403,628,191,-604,-407,870,-116,-344,125,-97,783,76,-742,-256,-310,672,947,-420,114,862,495,840,-335,834,506,-452,534,-710,-974,702,-530,446,625,567,-646,-660,-528,-493,-644,-887,727,-278,316,938,-754,651,-710,-85,-36,-763,-872,-705,743,922,676,-857,531,-560,-770,-274,-946,595,-203,-317,634,747,-214,-964,12,-815,419,464,-918,-989,-233,-675,-661,-790,919,760,-729,-84,-103,436,-789,-462,-961,266,-553,910,-466,-819,-847,791,188,162,-181,292,-573,772,-393,-22,586,-14,709,-835,155,316,169,660,-230,827,-354,-77,-148,-847,695,841,-861,-53,-857,49,900,265,-446,924,883,-66,-770,464,-134,290,-743,-830,843,-12,87,256,764,-79,297,-536,-107,967,492,60,-329,77,708,-257,857,568,862,841,-585,381,-31,289,927,-121,-822,98,318,290,732,125,-554,159,602,792,622,300,-314,-739,394,-878,33,143,717,-456,664,-358,496,929,256,334,151,800,-503,-102,738,-389,0,467,-36,-196,603,121,715,300,-963,-777,-943,747,250,-559,824,863,-846,890,834,-245,-211,870,-483,901,493,567,803,217,540,891,-22,728,755,885,-380,217,740,-976,-994,-641,-225,-135,551,346,-780,40,920,-372,312,-293,-360,494,15,257,368,58,-716,-589,362,88,458,321,350,-568,-881,-36,553,37,304,330,-351,-181,432,-772,-4,266,-211,630,-123,336,-381,538,546,799,317,2,-810,598,-528,-218,585,-346,-252,-865,-320,786,-643,-874,-398,-388,726,-995,-913,810,-242,372,-565,-123,-809,399,397,-648,-932,511,666,561,628,721,981,954,-257,840,-158,804,95,992,643,963,-650,20,-607,619,956,920,-600,-148,974,-188,632,-102,284,928,229,260,-764,-548,865,-202,688,-338,242,771,159,712,-47,-405,144,-834,289,951,847,-120,-19,984,219,119,807,-471,-693,-271,731,-1000,740,-266,909,-314,234,-881,188,-408,429,760,751,989,-568,-87,577,596,655,-66,562,-280,837,-934,-733,-951,941,571,-138,-48,402,-66,-584,-964,-332,723,808,324,174,-233,-861,-439,-605,128,-217,988,294,-174,378,-850,-492,802,96,-394,491,513,-693,-65,337,873,-773,-119,-187,-428,-949,-884,-434,127,348,173,-289,307,254,-294,-718,-759,-627,-61,-825,265,992,15,221,-78,939,-376,-92,174,-117,22,287,237,209,-303,428,-593,575,525,-551,658,748,542,-185,558,664,284,463,-80,529,534,964,-282,-527,-387,743,-59,-676,593,244,-21,178,-246,16,-53,402,-592,327,-47,-866,-981,-69,-163,-780,262,-907,514,347,285,-995,425,-619,-226,-70,612,-986,-55,-492,-531,945,-123,-229,-24,979,759,-27,-940,-240,-797,-357,-935,435,-696,-255,397,996,-18,638,-92,942,-941,-423,27,471,-467,-440,-782,-329,-751,826,-571,358,-153,-341,818,-257,-228,-104,-829,-683,-278,-60,-427,-818,-874,277,-360,-882,-194,787,583,-810,-858,96,-7,546,73,673,760,-482,-766,-206,-144,436,-715,572,-213,-134,-572,-623,730,324,-65,-615,92,-229,-468,-438,618,922,994,23,821,386,-182,347,-935,619,311,-638,798,270,671,679,-114,-519,355,128,98,-167,-721,-523,92,-463,-885,-108,-881,-805,710,852,60,9,745,-940,822,-156,-148,-225,702,313,111,231,-154,-874,622,875,-260,301,473,-944,-460,857,-807,-232,-903,228,935,-456,-657,661,-811,306,415,413,-160,621,715,215,787,-203,949,197,712,-283,364,615,392,227,516,-978,-172,531,693,-266,-207,402,-563,293,583,470,-164,-532,517,688,969,650,513,-404,555,932,772,390,461,570,-573,-272,-800,-461,665,-660,270,-708,-177,528,-464,592,223,-587,-67,-49,499,-75,933,-664,517,-119,437,-766,-653,-908,877,520,714,295,37,620,238,845,-105,-159,36,-157,124,-437,756,528,-184,-246,746,267,890,59,-958,394,-78,838,-115,282,-393,64,659,265,998,377,315,70,65,175,327,504,-265,-651,205,803,-839,-762,-611,-315,-134,-154,199,337,626,52,-991,-331,-57,-689,686,-112,-433,-272,903,717,-491,531,84,-977,386,509,-457,-33,458,354,-74,-737,-321,-53,-531,-534,-213,-147,547,-989,784,-560,775,442,-754,-417,883,370,-112,673,406,-826,780,133,-394,917,-646,142,-477,-964,851,-16,-246,958,635,888,11,-739,729,623,596,803,-639,186,-308,119,606,-35,-428,-625,612,-938,74,433,925,-866,984,683,-657,370,578,135,-954,348,-792,687,452,356,124,696,574,267,-505,141,527,454,739,-37,715,576,765,533,-972,-822,809,-405,718,973,-133,-181,-875,-466,90,-801,577,-488,-149,-33,-919,662,-766,929,812,737,-591,-231,258,-990,-925,21,-763,-873,474,901,983,762,-259,586,-862,-680,-485,-191,-344,-841,713,141,-515,-547,-541,-517,-544,-314,269,580,15,797,-496,62,-357,-615,58,987,127,285,-112,-802,-23,111,-927,704,-64,-385,-614,-397,510,155,938,91,-535,-761,261,-18,87,-321,748,-114,-168,-391,3,1,38,-988,494,-968,516,498,207,361,691,972,-844,497,824,-741,207,-690,-175,-847,219,-385,-471,391,436,642,423,-5,-201,929,-855,571,413,-398,569,-32,378,460,-103,177,910,716,641,-242,-327,11,-2,-878,431,918,728,327,798,-91,971,356,476,701,-107,-670,447,984,-928,251,394,-709,-924,-274,976,855,-613,914,423,574,880,293,-589,-870,-876,636,-880,-321,-128,-303,394,24,-989,-285,-716,251,399,-294,-432,-966,-607,146,580,-439,57,62,-267,-38,-163,106,-216,455,857,-157,-682,464,257,502,-165,121,-218,-628,993,-642,-355,176,-191,2,683,726,23,871,-552,-158,-848,496,514,377,855,498,-142,462,218,789,411,-730,432,-126,-939,746,-789,318,746,-801,588,407,546,-817,-698,-529,491,960,-975,-261,-73,421,433,-462,364,-80,61,2,-667,-556,-971,-367,-238,-255,-992,433,968,-856,-849,502,-529,-599,851,462,-866,168,251,263,-449,373,182,-888,397,560,-531,180,-866,298,-246,-141,506,-363,-309,23,373,-818,440,-142,-106,316,818,-659,743,-185,741,35,-572,-678,148,-503,-876,44,-773,120,114,-584,29,-165,93,-473,736,814,280,-921,168,-167,-177,-617,-614,195,-72,-25,-579,649,-762,-894,909,-111,158,-149,-817,-257,373,-762,-52,122,-612,-677,843,109,16,789,-203,122,-729,-987,-388,595,-638,964,-936,-512,184,-505,447,-206,342,-394,-717,-887,-124,-38,914,438,418,168,-767,-412,850,256,963,716,57,370,509,-733,-496,-666,960,227,8,176,-648,933,-622,-966,-416,-411,463,595,745,99,33,-965,934,884,-253,321,-384,-154,299,-927,109,-232,356,27,-114,501,-649,504,-410,-187,-341,-34,-774,189,850,496,-632,-262,931,-557,758,-818,-966,506,262,-201,-616,395,231,524,259,740,690,352,-547,988,-959,-848,638,-96,690,-327,362,-195,642,822,413,-296,974,865,931,-584,746,-146,24,354,725,45,-694,603,2,-918,-218,432,-19,239,-476,908,507,-268,695,412,-812,127,-914,-992,822,-703,558,-75,773,-313,622,534,-938,516,172,-803,214,-88,300,-911,5,-60,-56,670,-667,-980,481,-613,-556,222,-530,-901,-16,969,658,-765,727,793,-508,-980,579,-107,-363,-315,107,522,322,-576,-554,131,-395,-243,671,59,645,924,949,-951,-932,-962,-890,354,773,-389,-297,315,615,-767,-378,572,-163,968,391,853,-580,543,375,-823,-563,-333,575,-63,-223,756,-177,-111,-892,-461,-199,-954,-47,650,-243,37,890,495,-556,-139,199,-260,-400,500,-399,296,-79,-255,168,-381,-789,-404,425,-396,802,-514,971,-912,-962,-375,-261,-542,323,810,-320,-579,690,-582,118,-52,-296,719,859,574,-839,925,616,863,695,-552,-996,485,-210,-61,-252,-506,-327,554,-674,-775,310,727,715,16,-510,460,-1,-234,-841,391,841,-549,876,40,501,0,-630,310,373,-834,-196,-5,-168,373,-662,-923,-249,-899,717,-909,199,113,37,-145,-404,847,534,-251,893,-144,180,182,918,883,419,390,167,-985,-900,13,908,722,-646,-766,761,-652,516,330,352,281,666,-358,-672,-915,-67,493,-292,-64,-454,-216,325,-480,655,956,-385,-609,-538,-842,-100,838,-489,-706,519,414,199,55,-109,5,-569,99,-461,-178,-170,-713,583,-817,-864,765,-34,703,17,-531,784,-324,-333,317,-906,-883,923,995,896,-382,-455,-888,-942,-793,-549,-495,-658,-18,347,-689,-817,590,-848,-112,-36,-213,-39,-670,-430,-380,-549,-339,667,-23,-627,-52,202,221,-97,-355,-470,343,-942,-120,956,-127,326,539,-15,-189,567,446,427,253,509,703,-344,-535,-37,646,289,-160,523,-308,247,520,-870,-81,79,303,-481,549,-209,-65,894,64,959,-883,-499,729,-652,644,-416,-612,-422,525,287,92,91,713,639,-138,-947,-771,135,-254,-979,-131,724,612,878,520,-907,732,-432,-576,-879,-543,-387,371,955,-988,-702,-832,506,755,977,529,-231,401,683,401,301,232,-1000,18,113,793,963,-778,532,27,914,-461,-565,-483,-540,279,-260,129,-735,388,128,103,-499,-58,619,944,-109,-618,-71,550,452,529,53,-756,986,-101,718,-401,454,-807,63,-415,180,-79,-942,75,-991,923,761,-325,-213,176,-198,295,794,-141,686,956,930,846,565,-713,165,-486,669,377,-611,669,319,615,415,-233,40,-690,834,-944,495,414,23,-678,765,164,-822,-365,-81,-859,-706,-926,492,668,-678,-387,-616,610,697,-181,-897,412,121,446,618,144,538,-402,-657,701,528,-393,647,-305,-987,991,771,-453,-459,912,-603,-113,906,295,861,294,481,-362,867,947,-8,-721,-211,16,63,834,722,708,309,876,495,372,961,-387,947,56,-764,460,732,11,-582,604,-488,-563,-907,161,-550,304,-600,-319,112,930,-833,267,540,958,453,-600,-257,-878,847,-350,-464,123,688,484,192,880,504,234,941,-871,-636,-956,316,91,-650,-336,-750,887,-157,233,960,-633,-979,887,479,-290,577,-546,-125,110,-534,-222,985,-279,522,729,-150,-345,-704,-61,-100,823,-702,449,-187,-64,-851,164,251,-685,-301,380,966,-498,-781,949,-57,344,23,57,51,769,-386,548,-909,-830,-863,950,43,684,188,-181,924,298,-623,-10,426,98,981,447,-263,32,-104,27,-206,74,34,682,-259,235,91,369,-232,-493,-355,-62,-460,12,110,-422,513,-558,669,710,-406,-964,790,923,-936,-565,-410,-991,-962,285,903,444,-13,648,998,920,-912,901,-661,-720,-979,-542,85,-804,523,595,-396,480,-997,-611,-121,39,-227,-372,477,-426,-204,636,872,303,45,352,-697,185,160,516,-89,57,631,-840,-511,-395,-866,383,-458,188,-569,-321,861,-937,716,192,57,-50,-414,564,522,-169,494,-307,-745,-728,-990,-711,853,-139,597,-247,68,-759,-833,-245,400,-327,-94,-708,-602,-884,-442,-441,-817,-724,-560,751,-321,-887,-669,663,710,359,-344,149,448,589,-894,934,115,25,-709,-145,40,49,383,-892,-87,-247,-536,67,914,-931,-869,-683,-301,-918,-82,-672,435,-798,-438,-847,248,185,26,977,-784,-655,-587,109,-152,-634,-733,-677,839,-766,190,589,-717,-526,567,-482,-190,-966,884,497,-119,-671,-923,-328,840,332,498,-653,-442,-412,-556,-767,115,887,377,-338,-579,397,-969,537,831,-847,-426,585,990,-421,463,-35,-800,605,585,-969,286,-913,-897,577,951,-310,-575,-588,273,486,-290,-384,-132,-760,371,-66,86,-448,-981,24,-492,325,424,479,306,-149,567,-269,310,226,325,287,-787,-447,691,-310,128,895,506,-608,741,-388,264,784,-800,687,383,-264,-563,-478,-808,-906,-522,379,603,981,-69,-458,-390,-363,-509,136,-511,652,-19,-329,265,973,-780,-364,360,-1,-981,869,571,644,939,717,-260,289,205,-432,-126,-937,4,-382,293,805,-753,-216,-152,191,805,-86,-866,-1000,266,332,541,493,-89,-70,-204,845,-289,857,-394,848,822,-165,-682,-460,162,-222,573,263,-610,825,106,-796,-536,-445,-807,638,514,398,599,59,-87,-424,5,316,949,10,-267,703,579,437,-814,-429,-283,499,771,-666,-876,-240,21,923,-229,-540,167,754,376,425,110,-849,574,-207,-589,-645,-747,-435,465,-583,-71,780,-269,-43,-398,598,-900,-24,-309,909,981,-282,21,645,581,750,609,572,-836,-322,-896,312,675,-115,-233,-909,-960,-178,986,-298,864,387,880,785,420,-900,887,313,-590,-22,132,-256,698,-798,-697,493,485,-282,153,875,631,-260,445,788,-86,151,713,841,-784,533,646,520,-35,-127,856,-512,-278,-148,510,918,-888,-492,-691,-96,675,28,-185,-489,924,664,697,-367,-699,379,-245,108,642,894,922,-585,984,-592,812,-828,118,278,582,-810,238,-622,-932,361,454,-752,4,91,-195,976,-157,-7,-372,-864,271,760,99,788,-954,500,-547,-925,890,306,-852,-831,-337,-891,-729,-526,-130,-803,-111,165,-122,-666,-864,-298,-463,-321,-592,-714,625,-422,-714,135,946,-955,-951,542,955,-639,689,92,-371,-934,89,-348,617,-691,-966,674,127,-1000,792,584,-123,211,37,-844,568,354,-862,314,183,999,-955,508,-317,880,-366,935,-925,259,-627,-195,-542,-143,-593,285,782,970,-791,878,544,-332,-328,285,328,298,765,-581,-920,74,570,-991,916,-211,712,-46,-630,-500,-29,706,890,-473,640,-275,19,897,-887,93,-181,-611,-313,92,727,-703,580,928,-267,128,-894,126,-281,34,965,-961,238,-894,-83,860,158,-434,808,87,498,-890,671,846,-873,-211,-628,-637,-813,-270,-573,99,211,-358,-23,-564,-181,314,716,678,530,-937,306,-18,-397,699,-253,-393,-831,647,-186,810,537,294,689,848,-532,-198,-753,-749,372,657,492,-802,-178,169,826,-379,85,60,456,-52,-340,-292,550,170,-391,947,513,233,-377,-667,-48,-735,495,145,-59,-701,801,620,-837,-676,334,379,-452,-45,200,-444,-893,217,118,-487,688,-427,364,-315,224,-591,-436,-784,818,-140,765,673,-947,469,-161,-186,-44,-139,40,-744,-679,-853,719,452,412,-280,-528,-146,-217,770,-167,-662,-436,306,-756,755,-800,-608,-66,-530,887,-618,611,-661,-19,-871,-793,403,-590,741,167,458,431,-239,486,944,978,511,-210,382,161,613,802,769,302,150,-506,-182,-174,586,131,833,296,413,75,465,730,-645,620,-732,891,-18,98,570,531,723,-14,-582,639,325,-784,82,40,-483,17,986,-815,162,-430,767,-488,161,427,465,801,-384,-872,-705,-448,420,754,785,-81,-840,-200,-3,-646,-756,793,-474,-787,549,-627,-228,-49,-7,-284,-336,-632,602,5,-339,111,665,244,792,873,-14,796,273,884,-71,-388,-692,-295,409,-587,-319,835,-209,-498,724,-505,851,505,-39,-210,539,-23,597,573,819,-780,613,860,-545,488,554,-784,-299,-50,-943,611,-848,884,785,511,-73,102,98,297,551,-41,-792,-997,392,-550,-492,821,-227,-967,-756,220,846,-503,-906,915,852,897,269,203,-764,943,210,-685,-916,725,422,976,-599,-690,-697,-988,-477,-510,-707,432,-999,-414,688,391,-722,-390,-304,-929,-730,740,-221,564,319,431,421,-114,416,823,-138,-733,-143,702,380,-860,-214,-161,-577,-930,922,-835,-831,-327,-924,-875,99,2,400,-546,-62,515,-691,324,211,912,-774,726,848,-926,-385,-392,-910,-684,-418,794,141,-892,525,483,-211,602,644,743,93,665,-219,-913,-478,575,831,-288,873,743,-372,-226,-194,23,-207,251,507,877,357,-244,988,380,135,-523,-99,688,-924,-940,-731,934,-732,-644,986,-379,907,-185,-160,909,-755,415,-201,-836,969,-54,-866,-842,953,-345,-82,98,998,185,-583,-837,224,-497,867,51,-849,-332,-778,833,979,779,-986,-657,-72,763,-45,-409,659,686,148,-593,-266,-806,50,719,-375,-633,760,577,572,-204,539,-573,-245,45,-181,-153,-721,478,-386,-951,660,-74,89,303,424,-350,584,534,-699,989,-922,-743,-452,827,739,-243,-811,927,713,-12,-404,-181,-901,-849,-123,-574,-704,-252,-208,190,844,-920,-139,-640,71,139,-302,-169,440,482,702,854,68,663,850,-469,271,860,-795,442,-18,435,-2,-417,968,898,-317,-885,156,-182,619,904,-418,-733,971,270,-243,-39,531,356,980,-587,-301,883,-572,988,122,-635,-622,655,-680,-500,926,71,340,-582,496,427,-614,655,640,-745,-725,-103,231,-472,-661,577,-398,-951,-410,770,-9,-893,751,206,-425,-19,715,-502,-609,-774,224,206,-304,51,-824,-759,-11,-362,-538,-452,-47,-494,178,573,763,604,755,819,549,161,-440,-936,-318,-324,742,-166,718,922,-882,816,-738,785,-606,-57,389,-210,892,-297,299,-318,187,-276,367,375,219,546,19,-501,-755,526,-246,-266,140,-791,-379,187,270,-316,724,19,500,-281,-390,202,268,75,-923,-380,909,48,-115,-42,389,845,808,578,-148,-108,-511,420,357,-44,-974,-313,-855,874,-834,725,475,-926,-985,725,-370,-332,529,515,-317,-277,-731,534,-83,-9,538,5,890,771,-78,-556,199,-582,583,-571,-465,-294,-650,434,-558,991,-669,714,-620,3,-605,-804,451,643,455,-982,148,-244,-981,973,-951,587,-849,447,-895,-495,354,318,-614,-149,893,-142,-649,468,-639,-772,-314,-76,317,-479,-785,-765,582,-1000,-920,460,26,811,625,185,-194,523,-817,-604,-805,-829,-657,920,480,-924,58,728,-824,-428,558,-752,277,369,-884,342,15,-37,374,-565,-602,-736,-850,78,-702,-328,-862,68,-893,199,607,269,-242,85,778,-615,-348,-979,53,453,339,-206,429,109,-432,544,948,558,-667,-92,469,462,-280,512,350,-928,-546,-646,237,403,326,-662,-163,212,771,-459,-660,-903,33,-596,-137,-63,538,-592,-765,436,660,153,-442,267,31,-334,-800,508,-653,-800,682,46,281,-382,-487,884,856,343,438,346,407,857,-582,-689,580,146,995,-271,-310,968,-274,-787,575,826,-818,10,765,339,541,-438,-401,-931,-770,-83,117,-979,402,190,882,-669,95,572,-845,38,846,-593,653,279,-339,633,382,-273,-80,104,-640,-303,-929,568,189,652,-953,391,878,-6,-792,552,-609,669,529,130,-911,966,989,-309,-102,-188,71,780,-85,-226,149,790,-773,38,-368,-870,159,566,629,-484,108,767,243,445,479,508,10,-377,792,132,917,-646,581,110,-925,-98,571,-910,316,176,944,548,-757,-762,801,-369,766,200,-693,966,754,-243,959,-372,231,417,840,-731,324,613,-673,-983,11,57,607,55,-68,668,-53,-120,957,976,267,-743,-286,-179,-12,-420,-656,889,625,371,-931,-103,990,360,706,-82,-902,-349,167,-20,-582,203,-853,-154,394,-931,-116,-602,357,533,-373,275,-389,929,-16,-834,-125,672,717,-650,681,166,83,-191,316,-450,-362,634,-255,166,-444,-746,-195,785,134,842,951,-88,-357,409,-520,-342,35,-555,-585,801,-263,-233,-398,-139,323,109,417,772,737,-105,-559,-82,-58,-608,-214,153,790,-992,-761,-822,90,378,-160,-5,-292,-22,211,702,336,-230,874,754,-941,-950,669,-471,-769,226,-162,383,775,-924,222,-760,34,-175,-79,-232,-310,-919,-857,-187,-669,-137,-203,-286,901,762,-133,-43,141,100,79,72,294,164,134,563,-277,-715,-11,-482,545,737,-247,470,120,-751,211,824,-346,-449,659,-902,650,-131,-54,-625,-176,544,-519,-55,-488,318,-225,-95,-23,429,582,659,453,417,-254,768,489,2,-94,-812,131,-994,-735,914,425,722,-330,-135,767,-858,-809,514,-591,45,-786,46,411,933,-666,569,-682,-351,423,-304,880,883,-271,913,-199,-458,-776,958,-253,-726,-968,-797,559,313,842,764,-465,-747,-60,-371,-202,-45,265,365,706,961,180,-808,300,475,-423,-352,903,-400,-872,21,-782,852,-640,-335,643,732,794,92,61,-719,576,-337,464,943,-328,506,681,620,973,-184,-905,923,282,111,321,356,665,-124,-190,-153,611,530,208,161,509,-983,264,438,176,180,233,540,-563,-352,-501,428,200,678,194,-414,-449,482,-701,235,-779,929,-174,462,-912,263,659,260,265,706,-335,-584,322,78,-576,-587,276,-648,-272,-165,-96,2,-388,-487,640,302,103,-117,958,-52,875,-480,266,-821,-226,-915,-164,-396,-122,458,-803,-640,296,523,-656,-594,-705,-692,91,-783,759,821,-150,-419,-400,523,-598,-924,380,655,786,-272,-125,-595,-166,-821,461,470,-750,506,-597,-705,-901,27,162,338,248,-753,-710,-678,47,-323,-447,983,368,378,-833,905,-539,-37,787,976,-836,214,-907,-149,-656,-853,849,299,-450,-140,-461,-134,-394,208,-657,-851,283,-59,-567,-670,780,54,947,-930,214,-744,-974,378,-962,981,-120,-326,-800,-910,-270,-458,-480,58,-720,326,45,614,891,742,402,-325,415,-844,993,465,-211,-678,644,-742,-341,-940,812,-356,-885,769,719,-64,-481,42,715,-653,-350,23,151,-463,762,-727,-773,264,767,928,189,-192,-873,102,433,86,-316,-722,319,555,-268,-912,674,347,2,-305,264,465,623,-374,-620,-331,698,604,707,682,876,-96,-709,-387,-614,73,-601,466,338,-510,-175,744,220,728,-867,-159,498,-493,-900,-682,621,471,223,-576,-935,-799,582,-483,688,-468,-704,569,663,-36,-419,-787,734,-317,798,-361,-21,510,-929,-166,277,-577,-173,524,-951,55,423,851,-459,825,78,-363,-882,-499,185,-316,750,441,117,-532,973,-169,255,527,712,-800,-111,203,841,420,-906,-741,685,-334,-766,-525,721,640,248,663,122,460,-332,971,119,312,-189,264,-225,-937,545,-809,397,-183,505,-832,959,-656,-789,33,-341,-93,829,801,-862,-547,22,451,-52,-185,-472,-134,-272,240,-448,701,-529,158,314,-171,333,489,641,-431,690,-580,-306,23,760,-866,-351,-252,355,864,-739,529,-651,-12,982,-865,-33,-597,337,-455,-418,847,-112,-732,-678,159,925,-211,843,376,426,806,613,78,225,995,897,-327,-30,-474,-171,184,-69,-682,-766,180,571,176,-315,164,-363,852,-874,-606,-404,-88,581,452,639,668,-551,517,-646,152,-403,648,254,428,-856,587,617,345,731,-84,-115,886,637,-527,281,-962,-332,-381,-483,728,59,-576,101,689,917,381,-734,936,541,-832,538,-693,-596,204,-506,516,-458,-741,-496,600,401,-716,910,329,129,128,772,971,620,384,-293,-105,-313,469,-726,-735,-37,-738,-161,298,946,366,-113,-706,-817,269,-975,-953,447,-293,305,-544,-770,929,427,521,-324,-579,-176,78,201,822,793,-11,-231,830,293,196,521,591,-63,153,726,-194,618,-613,-179,-617,-163,930,330,-47,438,370,314,-305,101,-842,-726,7,797,-824,653,954,-299,-421,-619,735,929,870,189,-230,480,324,971,-726,-377,-169,106,-939,-276,484,-854,696,653,-708,-928,-923,447,220,243,-642,853,-343,-491,-930,-718,-561,-208,405,179,471,672,690,-891,442,-419,60,-438,722,101,-346,-30,-550,-990,970,-279,-787,-904,-70,-61,244,-558,-417,-575,-147,-894,-850,37,781,24,-569,-49,977,355,324,-706,102,568,7,-758,-58,678,-219,331,-415,-564,-893,313,-697,118,-826,498,170,990,-86,-924,793,284,-952,254,-142,-79,166,-394,-527,962,-526,998,-374,593,414,-276,221,-363,890,148,52,-739,569,421,-844,-656,-223,-675,408,301,-598,747,-392,30,-158,13,-213,121,-34,478,-303,436,420,581,867,751,-378,487,-242,-350,720,240,-967,989,995,409,636,-238,8,918,-748,520,-616,-869,547,936,71,-43,297,499,-56,-288,-107,886,-482,-400,838,57,719,956,-222,-703,-206,738,-797,-506,-668,429,-844,-125,-353,964,-438,97,-655,756,927,873,615,434,-581,533,-961,753,718,425,-999,-662,208,219,818,-782,-182,8,-247,415,-684,10,-232,432,193,92,-505,402,312,630,-502,446,-483,-442,-860,-560,866,-495,529,383,-870,-681,677,12,-358,-37,-701,613,763,-913,391,707,63,-748,623,315,463,-710,-53,-732,-804,36,835,-583,-946,448,596,453,-186,107,993,-103,304,162,-748,693,-120,508,-233,104,-973,-281,-55,833,951,-333,820,7,-260,892,-407,112,-392,909,-394,-794,-624,79,879,-53,469,-1000,12,370,-687,579,509,-986,11,-504,605,953,-342,474,-373,-935,385,-973,-500,59,30,-716,-714,-478,77,767,133,-986,70,522,746,-992,-215,-442,-514,219,192,102,80,-207,744,316,-196,-832,-16,55,-641,-774,127,800,-860,518,-329,-192,227,894,374,-396,-21,-101,663,-361,74,-830,451,144,-231,-441,-306,-555,549,625,901,373,787,24,-745,419,-45,-378,-796,981,268,100,835,88,675,-988,213,-27,-361,-533,980,441,148,-857,999,-679,379,458,-494,559,-359,-957,-584,283,-270,-858,-935,872,776,338,-89,-408,850,-941,416,951,-353,156,599,754,569,296,678,124,-246,-102,604,143,559,-419,873,812,-724,-338,-785,308,791,47,238,172,526,-556,731,-749,542,-906,-795,-220,289,44,-266,-134,725,839,710,-240,715,-661,-304,-57,641,-523,53,-131,-613,709,-87,-442,465,187,-220,-32,570,995,-649,44,610,-23,823,691,-433,995,-562,-373,354,103,-192,799,761,-130,-867,561,616,-969,-846,447,-502,-340,258,-554,-724,773,-144,228,713,-859,242,-144,-235,73,926,-745,-438,392,69,520,-722,-412,-472,8,-29,-313,-545,847,-379,363,-215,-198,982,-134,360,-901,231,193,-790,-164,98,-695,-509,-124,751,884,995,990,775,-46,-87,-886,849,-93,-205,-242,439,-175,929,471,812,-990,-299,449,978,-781,-576,-977,75,427,500,702,160,-440,156,631,620,692,167,-890,50,927,-762,-466,-237,102,-506,-458,553,987,-845,-239,818,295,-706,-983,426,-427,416,-509,534,-262,-729,-627,-489,-214,638,817,-589,152,589,-457,342,-168,-567,-927,280,419,-502,30,495,-805,772,-824,293,-398,-745,29,-898,-987,502,524,927,544,268,-204,-396,-651,-181,-679,-38,458,-517,-753,652,536,-233,45,272,-298,509,396,-590,245,-152,-304,-747,-221,262,-346,-452,-185,-680,-108,-590,190,105,401,558,-668,-319,511,295,913,-637,-833,231,-965,978,-598,-542,-818,928,-904,-201,131,-575,-944,-852,-647,895,563,-261,-369,254,-182,112,-54,705,-323,562,-65,776,-707,414,827,-187,-280,623,488,-461,600,-265,756,-841,-545,904,787,-866,-154,-454,40,-28,933,-295,-254,520,65,699,-178,110,-740,-711,-897,663,-755,-422,-327,947,-500,460,555,755,425,296,-503,-635,493,589,-767,375,-345,-870,-405,497,309,777,-26,481,-44,857,239,-173,424,510,-579,-605,713,57,-342,984,864,-371,-151,-740,-485,820,973,356,-569,700,-937,-9,830,-203,501,443,761,331,-224,-254,132,74,972,-1,444,-71,-874,-417,968,-104,-814,-995,-769,711,590,-114,-812,285,316,402,496,500,789,658,-442,144,675,168,-152,-288,-353,216,-477,144,-44,818,663,-164,946,-854,-522,-495,970,-523,836,424,954,888,335,-472,-730,128,-266,-834,210,700,210,711,-558,-211,122,573,-830,-933,434,-126,-483,947,-242,-547,-431,-917,414,-336,168,-289,-951,-421,399,869,400,614,329,-369,-504,888,829,-815,-940,940,665,-998,-154,248,460,669,431,559,226,-492,-326,545,-955,61,848,-350,653,950,813,-213,-493,-973,-126,-471,-58,-713,-443,-905,-273,-956,-986,-550,609,649,824,-144,857,440,264,-306,-688,-679,848,-370,-229,967,-664,909,-32,71,-769,459,-168,859,-942,984,393,918,-651,740,-749,871,112,766,-829,670,-205,419,-612,449,264,-753,-83,-920,704,-924,633,-863,-425,-419,402,349,801,-370,573,-647,116,-700,92,-640,29,473,11,-6,-536,862,-102,195,76,533,587,-35,45,-772,422,-47,194,156,254,281,951,870,-733,-568,-749,-756,166,-443,737,-147,-14,-998,487,944,-15,-272,557,-69,722,74,-631,729,5,-712,-236,-42,96,-165,41,473,-860,-971,668,-929,739,102,506,134,802,772,697,-180,-552,732,669,687,240,575,-567,-910,-32,-926,-912,-179,727,-779,751,-277,622,-357,550,965,-599,916,194,418,-993,634,646,14,-260,-850,-732,646,716,-805,984,804,578,31,628,-865,897,-153,646,-807,731,-720,-594,-698,423,88,-490,825,-915,143,185,359,582,-761,-503,-366,-547,-994,-418,570,343,290,-776,-316,779,-425,-983,173,1,-65,-498,238,485,-338,-342,-113,-896,213,-141,237,424,59,-415,406,22,-629,787,-703,-127,219,705,657,-829,330,-523,458,27,-826,735,-999,-629,574,694,-159,-83,-289,965,774,-39,541,226,816,-112,-186,-758,405,-366,-807,701,924,-486,40,-119,341,-7};
//        SubarraySum subarraySum = new SubarraySum();
//        System.out.println(subarraySum.subarraySum(str,-682));
    }
}
